Boruvka 和 Kruskal 在查找 MST 方面的差异

Question

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

他们的共同点：

• 两者都在无向图中找到最小生成树（MST）
• 两者都将最短边添加到现有树中，直到找到 MST
• 两者都从整体上看待图，这与 Prims 算法不同， Prims算法将一个又一个节点添加到 MST 中
• 两种算法都是贪婪的

唯一的区别似乎是，Boruvka 的视角是每个单独的节点（从那里寻找最便宜的边），而不是查看整个图（像 Kruskal 那样）。

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

Answer 1

你的描述是准确的，但有一个细节可以澄清：Boruvka算法的视角是每个连接的组件而不是每个单独的节点。

您对并行化的直觉也是正确的——本文有更多细节。摘要摘录：

在本文中，我们针对任意稀疏图设计并实现了四种并行 MST 算法（Boruvka 的三种变体加上我们的新方法），与最佳顺序算法相比，这些算法首次提供了加速。