java - 利用线程实现克鲁斯卡尔算法

Question

我正在实现 Kruskal 的算法，我想利用线程。但是我不确定我对算法的了解是否足以做到这一点。

我想我会在最后解决并连接图表的不同部分。谁能指出我正确的方向？谢谢。

Answer 1

来自维基百科

研究集中在以高度并行的方式解决最小生成树问题。使用线性数量的处理器，可以在 O(logn) 时间内解决问题。David A. Bader 和 Guojing Cong 在 2003 年发表的一篇论文“Fast Shared-Memory Algorithms for Computing the minimum Spanning Forest of Sparse Graphs”展示了一种实用算法，它在 8 个处理器上计算 MST 的速度比优化的顺序算法快 5 倍。 [9] 通常，并行算法基于 Boruvka 算法——Prim 算法，尤其是 Kruskal 算法不能很好地扩展到额外的处理器。

因此，您可能会研究该论文中提到的算法，但 Kruskal 可能不会从多线程中受益。

Answer 2

Kruskal 的 MST 算法很难并行化，因为它以严格指定的顺序考虑边。您应该看一下Boruvka 的算法，该算法更容易并行化，因为它可以独立地处理部分 MST 的每个子树。