algorithm - 在哪种情况下使用哪种最小生成树算法

Question

我是最小生成树的新手，并试图找出在任何特定情况下使用哪种 MST 算法。任何人都可以在任何特定情况下提供一些示例，其中一种 MST 算法比其他算法更适合

Answer 1

看看这个pdf

快速总结（引用页面）：

“如果将 Boruvka 和 Kruskal 的算法应用于现实世界，显然会更有用，而 Prim 的运行时间随着图形的顺序增长太快，无法在串行处理环境中使用。”

“在这三种算法中，当考虑并行计算时，Boruvka 最有希望。它在设计上是可并行的，涉及在本地搜索最小的边，然后在每一步之后组合生成的树。多个计算机处理节点之间的任务划分将是“Boruvka 算法的逻辑扩展。但是，从本文可以看出，Kruskal 算法在串行环境中效率更高。”

Answer 2

我想说最小生成树问题的两个主要解决方案在图表的表示方式上有所不同。虽然Kruskal可以很好地处理边列表，但Prim的算法将更好地处理邻域列表。如果让我决定图形表示，我更喜欢实现 Kruskal，因为我发现它更容易实现，但在这方面差异真的很小——所以这取决于你。