我正在实现Kruskal算法，希望能够利用线程。然而我不确定自己是否了解足够的关于该算法的知识。
我的想法是将图的不同部分分别求解，并在最后连接起来。有谁可以指点我一下方向吗？谢谢。
2个回答
4
来自维基百科
研究重点是以高度并行化的方式解决最小生成树问题。使用线性数量的处理器可以在O(logn)时间内解决问题。David A. Bader和Guojing Cong在2003年发表的论文《用于计算稀疏图的最小生成森林的快速共享内存算法》演示了一种实用的算法，该算法可以在8个处理器上比优化后的串行算法快5倍计算MST [9]。通常，并行算法基于Boruvka算法，Prim和特别是Kruskal算法不太适合增加处理器。
因此，您可能需要查看该论文中提到的算法，但Kruskal可能无法从多个线程中获益。
- James Kolpack
0
Kruskal算法用于生成最小生成树，但由于它按照严格指定的顺序考虑边缘，因此很难并行化。您应该看一下Boruvka算法，因为它可以独立地处理部分最小生成树的每个子树，从而更容易并行化。
- Keith Randall
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接