When should I use Kruskal as opposed to Prim (and vice versa)?

Question

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?

Solution 1

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.

Solution 2

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.

Solution 3

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.

Solution 4

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²).

Solution 5

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.

View more solutions

Comments

[yairchu]

I would say "typical situations" instead of average.. I think it's an obscure term to use, for example what is the "average size" of a hash table? no idea.

[SplittingField]

Don't forget to add that Prim's + Fibonacci heaps gives an amortized running time, not a worst case running time.

[agorenst]

@SplittingField: I do believe you're comparing apples and oranges. Amortized analysis is simpy a way of getting a measurement of the function (so to speak) --- whether it is the worst case or average case is dependent on what you're proving. In fact (as I look it up now), the wiki article uses language that implies that its only used for worst-case analysis. Now, using such an analysis means that you can't make as strong promises about the cost of a particular operation, but by the time the algorithm is done, it will indeed by O(E+VlogV), even worst-case.

[Alexandru]

That sounds good in theory, but I bet few people can implement a Fibonacci heap

[Todd Gamblin]

Who needs to implement one? Just google for an existing implementation. Fibonacci heaps have been around since 1987.

[Green goblin]

@tgamblin, there can be C(V,2) edges in worst case. So, doesn't the time compleixty of Prim's algorithm boils down to O(V^2 + VlogV) i.e. O(V^2) in case of fibonacci heap?

[V G]

There is also another important factor: the output of Prims is a MST only if the graph is connected (output seems to me of no use otherwise), but the Kruskal's output is the Minimum Spanning forests (with some use).

[Will]

@AndreiI you can modify prim's algorithm slightly to get a forest on an unconnected graph. All you have to do is run the algorithm from all of the vertices its well explained in the Princeton online course algs4.cs.princeton.edu/43mst

[OJFord]

Nitpick: Last 'slide' in each should read "repeat until you have a spanning tree"; not until MST, which is something of a recursive task - how do I know it's minimal - that's why I'm following Prim's/Kruskal's to begin with!

[mikedu95]

@OllieFord I found this thread for having searched a simple illustration of Prim and Kruskal algorithms. The algorithms guarantee that you'll find a tree and that tree is a MST. And you know that you have found a tree when you have exactly V-1 edges.

[OJFord]

@mikedu95 You're correct, making the same point as my earlier comment from a different angle.

[enedil]

Also, if maximal weight of edges is small and discrete (preferably integers), then you can bucket sort edges in linear time, which amounts to O(E α(V)), where α is the inverse Ackermann function (in practical cases always less than 5, since this value is never obtained by predicted number of atoms in the universe).

[ani0904071]

But isn't it a precondition that you have to only choose with a single weight between vertices, you cant choose weight 2 more than once from the above graph, you have to choose the next weight ex:3 @Snicolas

[Yu Gu]

It looks to me that Prim is never worse than Kruskal speed-wise. Since E should be at least V-1 is there is a spanning tree. I think the reason we may prefer Kruskal for a sparse graph is that its data structure is way simple.

[Phasmid]

Did you mean Omega(V logE) for Kruskal's best case? Using a binary heap, we only need to perform (V-1) deletions in the best case (when none of the "shortest" V-1 edges forms a cycle). But, the length of our binary heap will start out as E.