algorithm - 并行最小生成树算法

Question

我知道一些最小生成树算法：Boruvka、Prim 和 Kruskal。其中哪些可以并行实现？

谢谢！

Answer 1

在这 3 种算法中，只有 Boruvka 算法可能很容易并行化。

引自algoritmy.net 上 Boruvka 算法的描述：

Borůvka 算法的一个显着优势是可以很容易地并行化，因为为每个组件选择最便宜的输出边缘完全独立于其他组件所做的选择。