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

Question

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.

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.

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

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

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.