Kruskal’s Minimum Spanning Tree Algorithm

The problem is to find the minimum weight spanning tree (i.e., a connected acyclic subgraph) of an undirected weighted graph. Kruskal’s algorithm finds the MST in time O(E log V). It is a greedy algorithm that always tries to add the next least-cost edge to the current set of edges in the MST if its addition does not create a cycle in the MST.

The algorithm can be described as follows:

sort edges in order of increasing cost
MST = {}
foreach edge (u, v) in order of increasing cost
if MST ∪ (u, v) does not create a cycle
add (u, v) to MST
return MST

Checking for cycles can be done with the help of union-find/disjoint set data structure. Initially, each vertex is in its own set. When we are trying to add an edge (u, v) to the MST, we first check if they belong to the same set in which case adding that edge will create a cycle. If they don’t belong to the same set, we add the edge to the MST and merge the sets containing the vertices u and v.

Running time analysis: Sorting takes time O(E log E) and each query to the union-find data structure takes time O(log* V). Since there are E such queries, the overall running time is O(E log E  + E log* V) = O(E log E) = O(E log V) (since E is at most V2) i.e., time for sorting dominates the overall running time of the algorithm. If the edges are already sorted, then running time reduces to O(E log* V).

Take a look at the C++ implementation.

Try your hand at problem MST, which uses this idea.

Reference: Algorithms 4th Edition by Robert Sedgewick and Kevin Wayne

20 thoughts on “Kruskal’s Minimum Spanning Tree Algorithm

  1. Pingback: Union Find / Disjoint Set data structure C++ implementation | Everything Under The Sun

  2. Pingback: Prim’s Minimum Spanning Tree Algorithm | Everything Under The Sun

  3. I was challenged by a professor of mine to implement this algorithm on a parallel machine. I haven’t done it, but I’m planning on doing so. Might be a hint! 🙂

  4. hey buddy i tried to implement this program and took contents of text file from mentioned site, it doesn’t gets executed it says kruskal.cpp stopped working..

  5. For prims doing this make works:- u=u-1; v=v-1;
    for kruskal doing this make works:-edges[i]->u=edges[i]->u-1; edges[i]->v=edges[i]->v-1;

    • Yes we can and it’s much easier to implement as well. It does not require Indexed priority queue and works with normal priority queue. Instead of changing the weight for reaching a new vertex (in eager version), we just add the new vertex with the reduced weight onto the queue. To understand their differences and see and implementation, look here:

  6. in line 14 of lazy prims i pasted freopen(“input1.txt”, “r”, stdin) and its working now, thanks for helping me..
    I would like to is there any way to calculate how much time these programs will take for vertices and edges more then 500 and 1000 ?

    • Complexity of MST problem is O(E log V), which is extremely fast. If you can store the graph in memory, you can find its MST very quickly so you’d be bounded by how much you can store in memory.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s