Kruskal’s Algorithm

A greedy approach to an Minimum Spanning Tree.
All edges are sorted in increasing order.

Essentially the idea is to take the “cheapest” edge you can as long as that edge does not form a cycle.

Without a DSU, from ECE406 I have this algorithm as well which doesn’t require the DSU:

1. E’ = {0}
2. repeat until all edges have been considered
3. add the shortest edge to E’ that does not create a cycle
4. end

Cut property

• Suppose the edges X are part of an MST of $G=(V,E)$ with length edges l
• Pick any subset $S\subset V$ such that no edge in $X$ crosses between $S$ and $V-S$
• If $e$ is the shortest edge crossing between $S$ and $V-S$, then $X\bigcup e$ is also a part of an MST of G

This cut is the partition of V into two groups, $S$ and $V-S$.

Useful property

Any connected and undirected graph with $E=V-1$ is a tree

Why does this work?

• Each each iteration $E^{\prime }$ is a partial solution X
• Each partial solution is a forest with connected trees (T)
• The next edge considered (e) is an edge with ends in different connected components
• Since e is the shortest edge that doesn’t create a cycle, it must be the shortest edge between $T_1$ and $V-T_1$, etc
• Therefore, e satisfies the cut property Since every edge added satisfies the cut property, $E^{\prime }$ is the MST at every iteration.

Now we need a good way to check if an edge creates a cycle…

We use a Disjoint Union Set to make step 3 fast to do so…

1. Sort all edges by weight (ascending)
2. Initialize a forest
3. Iterate over edges from smallest to largest
   1. If an edge connects two different trees, add it to the MST and merge those trees
4. Stop when you’ve added n-1 edges or run out of edges