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:

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.

20 thoughts on “Kruskal’s Minimum Spanning Tree Algorithm”

1. 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! 🙂

2. fdk says:

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

• Did you take the input from the sample test case given here: http://www.spoj.com/problems/MST/ ?
This problem supplies vertices in 1-based representation and the code takes vertices in 0-based representation. To make the code work for this problem, subtract off 1 from edges[i]->u and edges[i]->v after line 77.

3. fdk says:

Still having the same problem, i did like edges[i]->u-1;

• Add these two lines after line 77:
–edges[i]->u;
–edges[i]->v;

4. fdk says:

Contents of input1.txt file:-
4 5
1 2 10
2 3 15
1 3 5
4 2 2
4 3 40

5. fdk says:

ok, it is working now. But in case of prims it shows like zero for both.

• It’s working with Prim’s as well. Just add this line after line 116:
–u; –v;

6. fdk says:

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;

• Yeah. I’ve already mentioned that in my replies.

7. fdk says:

yes thanks , can you please tell me if eager version can be changed to lazy or not ?

• 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: http://algs4.cs.princeton.edu/43mst/

8. fdk says:

OK so I went through the link, now what all should I change to make it as a lazy version ?

9. fdk says:

Ok, but the above code doesn’t takes any file so theres is no output.

• For that, you just need to write this line at line 14:
freopen(“input.txt”, “r”, stdin);
and give input in a file named “input.txt”.

10. fdk says:

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.