实现Kruskal算法利用线程

Question

我执行Kruskal算法，我想利用线程。但是我不知道我知道的算法来做到这一点就够了。

我想象的是，我最好的图形的不同部分会被解出，并在一端连接。任何人都可以点我在正确的方向？感谢。

Answer 1

从维基百科

  

研究都集中在解决   最小生成树问题在   高度并行的方式。随着   处理器的线性数量是   可能解决问题   O（LOGN）的时间。 2003年的论文“快   共享存储器算法计算   稀疏的最小生成森林   图”由大卫·贝德和郭经理   丛证明务实   算法，该算法可以计算MSTS 5   在不同于8个处理器倍的速度   优化的顺序算法。[9]   通常，并行算法是   基于Boruvka的算法，普里姆的   特别是Kruskal算法做   没有规模，以及额外的   处理器。

所以，你可能会考虑在该文件中提到的算法，但克鲁斯卡可能不会从多线程中获益。

Answer 2

Kruskal算法为MST是硬并行化，因为它在一个严格规定的顺序考虑的边缘。你应该看看 Boruvka 的算法更容易为并行它可以在一个局部MST独立的每个子树的工作。