Kruskal vs Prim

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?

Answer 1

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.

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

Answer 3

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

graph like this _____________ | | | | | | |__________| | Give name to any vertex a,b,c,d,e,f .

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

Answer 5

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

Answer 6

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.