algorithm - Boruvka 和 Kruskal 在寻找 MST 方面的区别

我想知道 Boruvkas 算法和 Kruskals 算法之间的区别。

他们有什么共同点:

都在无向图中找到 minimum spanning tree (MST)

都将最短边添加到现有树中，直到找到 MST

都从整体上查看图表，不像例如Prims 算法，将一个节点一个接一个地添加到 MST

两个算法都是贪婪的

唯一的区别似乎是，Boruvkas 的观点是每个单独的节点(从那里寻找最便宜的边)，而不是查看整个图(就像 Kruskal 那样)。

因此，Boruvka 似乎应该相对容易并行执行(与 Kruskal 不同)。真的吗？

最佳答案

您的描述是准确的，但可以澄清一个细节:Boruvka 算法的观点是每个连接的组件而不是每个单独的节点。

你对并行化的直觉也是对的——this paper 有更多细节。摘自摘要:

关于algorithm - Boruvka 和 Kruskal 在寻找 MST 方面的区别，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/49968046/