logo标签列表

何时应使用Kruskal算法而不是Prim算法（反之亦然）？

algorithmgraph-theoryminimum-spanning-treeprims-algorithmkruskals-algorithm
246

我想知道何时应该使用Prim算法和Kruskal算法来寻找最小生成树？它们都有易于理解的逻辑，相同的最坏情况，并且唯一的区别是实现可能涉及略微不同的数据结构。那么决定性因素是什么？

10个回答
246

如果你有一个边数众多的图，可以使用Prim算法。

对于一个有V个顶点和E条边的图，Kruskal算法的运行时间为O(E log V)，而如果使用斐波那契堆(Fibonacci Heap), Prim算法可以在O(E + V log V)的摊销时间内运行。

当图是密集图，边数远大于顶点数时，Prim算法在极限情况下明显更快。在典型情况（稀疏图）下，Kruskal算法表现更好，因为它使用更简单的数据结构。

10
我会将"average"翻译为"一般情况"或"典型情况"。我认为这个词用起来比较模糊，例如“哈希表的平均大小”是多少？我不知道。 - yairchu
3
我相信你正在把事情弄混。摊销分析只是一种获取函数（可以这么说）的测量方式，它是最坏情况或平均情况取决于你要证明什么。实际上（我现在查阅了一下），维基百科文章使用的语言意味着它仅用于最坏情况分析。现在，使用这种分析意味着您无法对特定操作的成本作出如此强烈的承诺，但是等算法完成时，即使是最坏情况，它的时间复杂度也确实为O（E+VlogV）。 - agorenst
17
理论上听起来很不错，但我打赌只有少数人能够实现斐波那契堆。 - Alexandru
3
在最坏情况下，可能会有C（V,2）条边。所以，Prim算法的时间复杂度难道不会简化为O（V^2 + VlogV），即在使用斐波那契堆的情况下为O（V^2）吗？ 答案：是的，最坏情况下可能有C（V，2）条边。因此，在使用斐波那契堆的情况下，Prim算法的时间复杂度可以简化为O（V^2 + VlogV），即O（V^2）。 - Green goblin
11
还有一个重要因素：只有在图形是连通的情况下，Prim算法的输出才是最小生成树（否则输出对我来说似乎没有用处），但Kruskal算法的输出是最小生成森林（有一定用途）。 - V G
显示剩余6条评论
137
我在网上找到了一个非常好的帖子，以非常简单的方式解释了它们之间的区别: http://www.thestudentroom.co.uk/showthread.php?t=232168。
Kruskal算法将通过添加下一个最便宜的边来从最便宜的边增加解决方案，前提是它不会创建循环。
Prim算法将从随机顶点开始增加解决方案，即不在解决方案中但通过最便宜的边与其相连的下一个最便宜的顶点。
这里附有关于该主题的有趣表格。 enter image description hereenter image description here 如果您使用最佳形式的Kruskal和Prim进行实现：分别采用联合查找和斐波那契堆，则会注意到Kruskal相比Prim更容易实现。
使用斐波那契堆的Prim更难，主要是因为您必须维护一个记录图节点和堆节点之间双向链接的簿记表。使用Union Find则相反，结构很简单，甚至可以直接以几乎没有额外成本产生mst。
4
Nitpick: 每个“幻灯片”最后都应该写上“重复直到生成树”，而不是生成最小生成树（MST），这是一个递归任务 - 我怎么知道它是最小的 - 这就是为什么我一开始就遵循Prim/Kruskal算法的原因！ - OJFord
1
@OllieFord 我找到了这个帖子，因为我在寻找Prim和Kruskal算法的简单示例。这些算法保证你会找到一棵树，并且该树是MST。当你有恰好 V-1 条边时，你就知道你已经找到了一棵树。 - mikedu95
@mikedu95 你说得对，只是从不同的角度表达了我之前的评论。 - OJFord
但是，这不是一个前提条件吗？您必须在顶点之间仅选择单个权重，不能从上面的图中多次选择权重2，您必须选择下一个权重，例如：3 @Snicolas - ani0904071
38

我知道您没有要求这个，但是如果您有更多的处理单元，您应该始终考虑使用波罗夫卡算法，因为它可能很容易地并行化-因此它具有比Kruskal和Jarník-Prim算法更高的性能优势。

37

Kruskal 的最坏时间复杂度是 O(E log E)，因为我们需要对边进行排序。 Prim 的最坏时间复杂度是 O(E log V)，使用 优先队列 可以得到更好的结果，甚至可以达到 O(E+V log V) 使用 Fibonacci Heap. 当图中的边很少时，比如 E=O(V)，或者已经排好序或者可以在线性时间内排序时，应该使用 Kruskal 算法。 当图中的边很多时，比如 E=O(V²) 时，应该使用 Prim 算法。

1
在我看来，Prim算法在速度方面从未劣于Kruskal算法。由于E至少应该是V-1，因此存在生成树。我认为我们之所以更喜欢Kruskal算法用于稀疏图的原因是它的数据结构非常简单。 - Yu Gu
28

Kruskal算法的性能会更好，如果边可以在线性时间内进行排序，或者已经有序。

如果边数与顶点数之比较高，则Prim算法更优。

27
如果我们在Prim算法的中间停止执行，它总是会生成一棵连通树；而另一方面，Kruskal算法可能会生成不连通的树或森林。
5

Kruskal算法的一个重要应用是在单链聚类中。

考虑有n个顶点和一个完全图。为了获得k个这些n个点的聚类，运行Kruskal算法在排序后的边集的前n-(k-1)条边上。你将获得具有最大间距的图的k个聚类。

4

Kruskal算法的最佳时间复杂度为O（E logV）。使用fib堆优化后的Prim算法可以达到O（E+V lgV）。因此在稠密图上，Prim算法更好。

你是不是指Kruskal算法的最优情况下使用Omega(V logE)？使用二叉堆，在最优情况下我们只需要执行(V-1)次删除操作（当“最短”的V-1条边都没有形成环路时）。但是，我们的二叉堆的长度将从E开始。 - Phasmid
2
在Kruskal算法中，我们有一个给定图形上的边数和顶点数，但在每条边上我们都有一些值或权重，根据这些值可以准备一个新的图形，该图形必须不是循环的，也不会从任何一侧关闭。
例如：
graph like this 
                  _____________
|                |                     |
|                |                     |
|__________|                     |

给任何一个顶点命名为a、b、c、d、e、f。
2

在更密集的图中，Prim算法表现更好，而且我们在添加边时不需要过多关注环路问题，因为我们主要处理的是节点。在复杂的图形情况下，Prim算法比Kruskal算法更快。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接