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

algorithm graph-theory minimum-spanning-tree prims-algorithm kruskals-algorithm
ebe picture ebe · Jul 28, 2009 · Viewed 185.6k times · Source

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

Todd Gamblin picture Todd Gamblin · Jul 28, 2009

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.

Related questions

Why do we need a priority queue in Prim's Algorithm

As my question speaks I want to know why do we use Priority queue in Prim's Algorithm? How does it saves us from using the naive way (yes I've heard of it but don't know why). I'd be very happy …

Read More
Use Dijkstra's to find a Minimum Spanning Tree?

Dijkstra's is typically used to find the shortest distance between two nodes in a graph. Can it be used to find a minimum spanning tree? If so, how? Edit: This isn't homework, but I am trying to understand a question …

Read More
Update minimum spanning tree with modification of edge

A graph (positive weight edges) with a MST If some edge, e is modified to a new value, what is the best way to update the MST without completely remaking it. I think this can be done in linear time. …

Read More