并行联合查找算法

Question

我需要并行kruskal算法，序列版本使用联合查找算法来检测无向图中的周期。有什么办法可以将这部分代码并行化吗？

Answer 1

那么，它可以在一定程度上并行化。它如下：

最初所有的边都按照升序排序。有一个main thread实际上从头开始扫描每条边，并决定添加当前边是否形成循环。我们并行化算法的主要目的是使这些检查平行。

这是我们使用worker threads的地方。每个线程都有一定数量的边进行检查，每个线程在每次迭代后检查其边是否与当前表示形成循环（迭代表示主线添加新边）。当主线程继续添加边时，一些线程会看到某些边已经与当前表示形成一个循环。

这样的边缘被标记为discarded。当主线程到达这样的边缘时，它会简单地移动到下一个边缘，而不进行任何检查。

因此，我们实际上使这些检查并行，这意味着算法运行迅速提高效率。

实际上，有一个nice paper使用了上述相同的想法。

编辑：

如果你非常在意过的所有算法的运行时间，你甚至可以使用并行排序算法最初是作为@ jarod42建议。