Kruskal’s algorithm

This is an algorithm to solve the MST problem. It uses the union-find data structure to help it identify cycles.

Pseudocode

Kruskal's(G,w):
	Input: undirected graph G=(V,E) with weights w(e).
	Output: MST edges X
1. Sort E by weights, smallest to largest
2. Set X to be empty
3. For e = (v,w) in E (ordered)
	1. If X U e does't have a cycle then X = X U e.
4. Output X

Run time

For step 1, we use merge sort so this takes time. Though as , we can think of this as .

Step 3, has steps in each one we run two operations in the union-find data structure both of which take time. So this is .

So in total this takes .

Correctness

We prove by induction on the size of that this must be a subset of some MST.

Base case

.

Note there must be an MST and . Therefore and we have shown it true for the base case.

Induction case

Suppose for some MST .

Suppose we want to add some edge . Let be the connected component of containing . Note as contains no cycles.

This forms cut with . is of minimum weight otherwise we would have added that edge already.

Therefore by the cut property is contained in some MST .

This proves the induction case and we have that is always a subset of some MST.

Conclusion

As the algorithm considers adding every edge and adds it if and only if it doesn’t add cycle the output is a spanning tree. This is also minimal as is always a subset of an MST giving the algorithm is correct.