寻找最小生成树中Boruvka算法和Kruskal算法的区别

Question

我想了解Boruvkas算法和Kruskals算法之间的区别。

它们的共同点：

- 都能在无向图中找到最小生成树（MST）。 - 都将最短的边添加到现有树中，直到找到MST。 - 都会全局查看图形，不像Prims算法那样逐个向MST添加一个节点。 - 两种算法都是贪心算法。

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

因此，似乎Boruvka在并行方面应该相对容易（不像Kruskal）。这是真的吗？

- User12547645

Answer 1

在 Kruskal 算法中，首先我们希望将所有边从最便宜的到最昂贵的排序。然后在每一步中，我们删除最小权重的边，如果它不在我们的图中创建循环（最初由 |V|-1 个单独的顶点组成），则将其添加到 MST 中。否则，我们只需将其删除。

Boruvka 算法寻找每个组件（最初是顶点）的最近邻居。它继续选择每个组件中最便宜的边，并将其添加到我们的 MST 中。当我们只有一个连接的组件时，它就完成了。

可以很容易地并行地找到每个节点/组件的最便宜的出边。然后我们可以合并新获得的组件并重复查找阶段，直到找到 MST。这就是为什么这个算法在找到 MST 的情况下是并行性的良好示例。

关于使用 Kruskal 算法进行并行处理，我们需要严格按顺序保留和检查边，因此很难实现显式并行性。它是相当顺序的，我们无法做太多改变（即使我们仍然可以考虑例如并行排序）。尽管有一些方法来以并行方式实现此方法，但这些论文很容易找到以检查其结果。

- mtszkw

Answer 2

您的描述是准确的，但有一个细节可以澄清：Boruvka算法的视角是每个连通分量，而不是每个单独的节点。

您对并行化的直觉也是正确的 - this paper 中有更多细节。摘自摘要：

“在本文中，我们为任意稀疏图设计和实现了四种并行MST算法（Boruvka的三个变体加上我们的新方法），这是第一次与最佳顺序算法相比获得加速。”

- k_ssb

---

非常感谢您的回答。 - User12547645

Answer 3

Boruvka算法与Kruskal或Prim的重要区别在于，使用Boruvka算法不需要预先对边进行排序或维护优先队列。

Boruvka仍然会在成本中产生额外的log N因素，但它通过需要对边进行O(log N)次遍历来实现。

您可以并行化Boruvka算法，但也可以并行化排序，因此我不知道Boruvka在实践中是否比Kruskal更具优势。

- Matt Timmermans