我想知道什么时候应该使用Prim 的算法，什么时候使用Kruskal 的算法来找到最小生成树？它们都有简单的逻辑，相同的最坏情况，唯一的区别是实现可能涉及一些不同的数据结构。那么决定因素是什么？
ebe
问问题
206697 次
10 回答
228
当你有一个有很多边的图时，使用 Prim 算法。
对于具有V个顶点E边的图，如果您使用Fibonacci Heap，Kruskal 的算法在O(E log V)时间内运行，而 Prim 的算法可以在O(E + V log V)摊销时间内运行。
当你得到一个边比顶点多得多的非常密集的图时，Prim 的算法在极限情况下要快得多。Kruskal 在典型情况（稀疏图）中表现更好，因为它使用更简单的数据结构。
于 2009-07-28T18:36:55.007 回答
121
我在网上找到了一个非常好的线程，它以非常直接的方式解释了差异：http ://www.thestudentroom.co.uk/showthread.php?t=232168 。
Kruskal 的算法将通过添加下一个最便宜的边缘从最便宜的边缘生成解决方案，前提是它不会创建循环。
Prim 的算法将通过添加下一个最便宜的顶点（当前不在解决方案中但通过最便宜的边连接到它的顶点）从随机顶点生成解决方案。
此处附上有关该主题的有趣表。
如果您以最佳形式同时实现 Kruskal 和 Prim：分别使用 union find 和 finbonacci heap，那么您会注意到与 Prim 相比，Kruskal 易于实现。
Prim 使用斐波那契堆更难，主要是因为您必须维护一个簿记表来记录图节点和堆节点之间的双向链接。而Union Find则相反，结构简单，甚至可以直接产生mst，几乎不需要额外的成本。
于 2014-01-26T00:23:54.830 回答
36
我知道你没有要求这个，但是如果你有更多的处理单元，你应该总是考虑Borůvka 的算法，因为它可能很容易并行化 - 因此它比 Kruskal 和 Jarník-Prim 算法具有性能优势。
于 2012-03-03T22:14:44.300 回答
31
Kruskal时间复杂度最坏的情况是O(E log E)，这是因为我们需要对边进行排序。 Prim时间复杂度最坏的情况是O(E log V)与优先队列，甚至更好，O(E+V log V)与Fibonacci Heap。我们应该在图稀疏时使用 Kruskal，即边数较少，如 E=O(V)，当边已经排序或者我们可以在线性时间内对它们进行排序。我们应该在图形密集时使用 Prim，即边数很高，例如 E=O(V²)。
于 2016-06-06T12:34:54.920 回答
27
如果边可以在线性时间内排序，或者已经排序，Kruskal 可以有更好的性能。
如果顶点的边数很高，则 Prim 会更好。
于 2009-07-28T18:43:52.497 回答
21
如果我们在中间 prim 算法中停止算法总是生成连通树，但另一方面 kruskal 可以给出不连通树或森林
于 2013-04-03T17:21:27.310 回答
5
Kruskal 算法的一个重要应用是单链路聚类。
考虑n个顶点，你有一个完整的图。要获得那些n个点的k个簇。在排序的边集的前n-(k-1)条边上运行Kruskal算法。你获得图的k-cluster最大值间距。
于 2013-09-08T05:45:52.367 回答
3
Kruskal 的最佳时间是 O(E logV)。对于 Prim 使用 fib 堆，我们可以得到 O(E+V lgV)。因此，在密集图上，Prim 的要好得多。
于 2011-10-14T01:34:42.533 回答
2
Prim 更适合更密集的图，在这方面我们也不必通过添加边来关注循环，因为我们主要处理节点。在复杂图的情况下，Prim 的速度比 Kruskal 的快。
于 2013-11-23T01:57:31.313 回答
2
在 kruskal 算法中，我们在给定图上有边的数量和顶点的数量，但是在每条边上我们都有一些值或权重，我们可以代表它准备一个新图，该图必须不是循环的或从任何一侧都不能接近 例如
graph like this
_____________
| | |
| | |
|__________| |
为任何顶点 a,b,c,d,e,f 命名。
于 2016-04-17T01:56:42.957 回答