我什么时候应该使用 Kruskal 而不是 Prim（反之亦然）？
I was wondering when one should use Prim's algorithm and when Kruskal's to find the minimum spanning tree? They both have easy logics, same worst cases, and only difference is implementation which might involve a bit different data structures. So what is the deciding factor?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（11）
如果我们停止中间的算法，prim 的算法总是生成连接的树，但另一方面 kruskal 可以给出断开的树或森林
If we stop the algorithm in middle prim's algorithm always generates connected tree, but kruskal on the other hand can give disconnected tree or forest
Kruskal 算法的一个重要应用是单链接聚类。
考虑 n 个顶点，您就有一个完整的图。要获得这 n 个点的 k 个簇。对已排序边集的前 n-(k-1) 个边运行 Kruskal 算法。您将获得图的 k 个簇，其最大值为间距。
One important application of Kruskal's algorithm is in single link clustering.
Consider n vertices and you have a complete graph.To obtain a k clusters of those n points.Run Kruskal's algorithm over the first n-(k-1) edges of the sorted set of edges.You obtain k-cluster of the graph with maximum spacing.
克鲁斯卡尔的最佳时间是 O(E logV)。 对于 Prim 使用 fib 堆，我们可以得到 O(E+V lgV)。 因此，在密集图上，Prim 的效果要好得多。
The best time for Kruskal's is O(E logV). For Prim's using fib heaps we can get O(E+V lgV). Therefore on a dense graph, Prim's is much better.
Prim 更适合更密集的图，在这种情况下，我们也不必通过添加边来过多关注循环，因为我们主要处理节点。 在复杂图的情况下，Prim 的速度比 Kruskal 的速度更快。
Prim's is better for more dense graphs, and in this we also do not have to pay much attention to cycles by adding an edge, as we are primarily dealing with nodes. Prim's is faster than Kruskal's in the case of complex graphs.
在克鲁斯卡尔算法中，我们在给定图上有边数和顶点数，但在每条边上我们都有一些值或权重，代表我们可以准备一个新图，该图必须不是循环的或与任何边都不接近
例如，
为任何顶点 a,b,c,d,e,f 命名。
In kruskal Algorithm we have number of edges and number of vertices on a given graph but on each edge we have some value or weight on behalf of which we can prepare a new graph which must be not cyclic or not close from any side
For Example
Give name to any vertex a,b,c,d,e,f .
在连通图中，我们有：
“
In a connected graph, we have:
“????” is the number of edges, and “????” is the number of vertices.
)
If ???? was close to the lower bound, Kruskal is a better choice. because the Kruskal complexity in this case is:
On the other hand, if ???? was close to the upper bound, Prime is a better choice:)
Kruskal complexity in a dense graph is:
)
N.B. Borůvka's algorithm performance with)
run-time complexity is almost similar to the Prime but better in some scenarios. The Reverse-Delete algorithm also has almost the same performance as the Kruskal algorithm with the following complexity: %5E3))
but in general Kruskal has a better performance.
The key point is that we should pick a solution by considering both number of edges and vertices.
我在网上发现了一个非常好的线程，它以非常简单的方式解释了差异：http://www .thestudentroom.co.uk/showthread.php?t=232168。
克鲁斯卡尔算法将通过添加下一个最便宜的边来从最便宜的边生成解决方案，前提是它不会创建循环。
Prim 的算法将通过添加下一个最便宜的顶点（当前不在解决方案中但通过最便宜的边与其连接的顶点）从随机顶点生成解决方案。
这里附上关于该主题的有趣表格。
如果您以最佳形式实现 Kruskal 和 Prim：分别使用并集查找和 finbonacci 堆，那么您会注意到相比之下，Kruskal 是如何容易实现的到普里姆。
Prim 对于斐波那契堆来说比较困难，主要是因为你必须维护一个簿记表来记录图节点和堆节点之间的双向链接。 而Union Find则相反，结构简单，甚至可以直接产生mst，几乎不需要额外的成本。
I found a very nice thread on the net that explains the difference in a very straightforward way : http://www.thestudentroom.co.uk/showthread.php?t=232168.
Kruskal's algorithm will grow a solution from the cheapest edge by adding the next cheapest edge, provided that it doesn't create a cycle.
Prim's algorithm will grow a solution from a random vertex by adding the next cheapest vertex, the vertex that is not currently in the solution but connected to it by the cheapest edge.
Here attached is an interesting sheet on that topic.
If you implement both Kruskal and Prim, in their optimal form : with a union find and a finbonacci heap respectively, then you will note how Kruskal is easy to implement compared to Prim.
Prim is harder with a fibonacci heap mainly because you have to maintain a book-keeping table to record the bi-directional link between graph nodes and heap nodes. With a Union Find, it's the opposite, the structure is simple and can even produce directly the mst at almost no additional cost.
当您的图有很多边时，请使用 Prim 算法。
对于具有 V 顶点 E 边的图，Kruskal 算法的运行时间为 O(E log V)，Prim 算法的运行时间为 O(E + V log V) 摊销时间，如果您使用斐波那契堆 。
当你有一个边缘比顶点多得多的非常密集的图时，Prim 的算法在极限下要快得多。 Kruskal 在典型情况（稀疏图）中表现更好，因为它使用更简单的数据结构。
Use Prim's algorithm when you have a graph with lots of edges.
For a graph with V vertices E edges, Kruskal's algorithm runs in O(E log V) time and Prim's algorithm can run in O(E + V log V) amortized time, if you use a Fibonacci Heap.
Prim's algorithm is significantly faster in the limit when you've got a really dense graph with many more edges than vertices. Kruskal performs better in typical situations (sparse graphs) because it uses simpler data structures.
我知道您没有要求这个，但如果您有更多处理单元，您应该始终考虑 Borůvka 算法，因为它很容易并行化 - 因此它比 Kruskal 和 Jarník-Prim 算法具有性能优势。
I know that you did not ask for this, but if you have more processing units, you should always consider Borůvka's algorithm, because it might be easily parallelized - hence it has a performance advantage over Kruskal and Jarník-Prim algorithm.
Kruskal时间复杂度最坏情况是O(E log E)，这是因为我们需要对边进行排序。
Prim 时间复杂度最差情况是 O(E log V) 且优先级队列，甚至更好，O(E+V log V ）与斐波那契堆。
当图稀疏时，即边数较少，例如 E=O(V)，当边已经排序或者我们可以在线性时间内对它们进行排序时，我们应该使用 Kruskal。
当图很稠密时，即边数较多，如 E=O(V²) 时，我们应该使用 Prim。
Kruskal time complexity worst case is O(E log E),this because we need to sort the edges.
Prim time complexity worst case is O(E log V) with priority queue or even better, O(E+V log V) with Fibonacci Heap.
We should use Kruskal when the graph is sparse, i.e.small number of edges,like E=O(V),when the edges are already sorted or if we can sort them in linear time.
We should use Prim when the graph is dense, i.e number of edges is high ,like E=O(V²).
如果边可以在线性时间内排序，或者已经排序，Kruskal 可以有更好的性能。
如果顶点的边数较多，Prim 会更好。
Kruskal can have better performance if the edges can be sorted in linear time, or are already sorted.
Prim's better if the number of edges to vertices is high.