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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

I know that you did not ask for this  but if you have more processing units  you should always consider Boruvka s algorithm  because it might be easily parallelized - hence it has a performance advantage over Kruskal and Jarn  k-Prim algorithm

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

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

Examples related to algorithm

Examples related to graph-theory

Examples related to minimum-spanning-tree

Examples related to prims-algorithm

Examples related to kruskals-algorithm