什么时候应该使用Kruskal而不是Prim（反之亦然）？ [英] When should I use Kruskal as opposed to Prim (and vice versa)?

问题描述

我想知道何时应该使用 Prim的算法以及何时使用 Kruskal的可以找到最小的生成树？它们都有简单的逻辑，同样的最坏情况，唯一的不同是实现可能涉及一些不同的数据结构。那么决定因素是什么？

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?

推荐答案

当您的图具有很多边时，请使用Prim算法。

Use Prim's algorithm when you have a graph with lots of edges.

对于具有 V 个顶点 E 个边的图形，Kruskal算法在 O（E log V）中运行如果使用O（E + V log V）的摊销时间内运行。 noreferrer>斐波那契堆。

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的算法在极限上的速度明显更快。 Kruskal在典型情况下（稀疏图）表现更好，因为它使用了更简单的数据结构。

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.

这篇关于什么时候应该使用Kruskal而不是Prim（反之亦然）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！