c++ - 并行 union 查找算法

Question

我需要并行化 kruskal 的算法，串行版本使用 union find 算法来检测无向图中的循环。有没有办法并行化这部分代码？

Answer 1

嗯，它可以在某种程度上并行化。具体如下:

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

这是我们使用工作线程的地方。每个线程都被赋予一定数量的边来检查，其中每个线程在每次迭代后检查其边是否与当前表示形成循环(迭代意味着主线程添加新边)。随着主线程继续添加边，一些线程看到某些边已经与当前表示形成一个循环。

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

因此，我们实际上使这些检查并行进行，这意味着算法运行速度很快，从而提高了效率。

其实有一个nice paper使用与上述相同的想法。

编辑:

如果您非常关心整体算法的运行时间，您甚至可以像 @jarod42 建议的那样最初使用并行排序算法。