Minimum Spanning Trees

Before learning Kruskal's algorithm, we need a data structure that efficiently answers the question: 'Are these two elements in the same group?' The Union-Find (also called Disjoint Set Union or DSU) data structure solves this with two operations: Find(x) returns the 'representative' (root) of the group containing $x$, and Union(x, y) merges the groups containing $x$ and $y$ into one.

The naive approach uses a forest of trees where each node points to its parent. Find follows parent pointers to the root, and Union links one root to another. Without optimization, trees can become tall chains, making Find slow — $O(n)$ in the worst case.

Two optimizations make it blazingly fast:

1. -

   Union by rank: Always attach the shorter tree under the root of the taller tree. This keeps trees shallow — height is at most $O(\log n)$.

2. -

   Path compression: During Find, make every node on the path point directly to the root. This flattens the tree for future queries.

With both optimizations, each operation takes $O(\alpha(n))$ amortized time, where $\alpha$ is the inverse Ackermann function — a function that grows so incredibly slowly that for any practical input size (even $n = 10^{80}$, the number of atoms in the universe), $\alpha(n) \leq 4$. So in practice, each operation is effectively $O(1)$.

Worked example — Union-Find on vertices {A, B, C, D, E}:

• -Initially: each vertex is its own set: {A}, {B}, {C}, {D}, {E}
• -Union(A, B): merge → {A, B}, {C}, {D}, {E}. Root = A (or B, depending on rank)
• -Union(C, D): merge → {A, B}, {C, D}, {E}
• -Find(B): returns A (B's root)
• -Union(A, C): merge {A, B} and {C, D} → {A, B, C, D}, {E}
• -Find(D): returns A (with path compression, D now points directly to A)

Kruskal's algorithm takes a straightforward approach: sort all edges in the graph from cheapest to most expensive, then go through them one by one. For each edge, ask: 'Would adding this edge create a cycle?' If no, add it to the MST. If yes, skip it. To efficiently check for cycles, Kruskal's uses the Union-Find (also called Disjoint Set) data structure, which tracks which vertices are already connected. Initially, each vertex is its own 'component.' When you add an edge, you merge the two components (union). Checking if two vertices are in the same component (find) is nearly O(1) with path compression and union-by-rank optimizations. The total time is dominated by sorting the edges: O(E log E).

Prim's algorithm takes a different approach from Kruskal's: instead of considering edges globally, it grows the MST one vertex at a time from a starting point. Begin with any vertex, then repeatedly find the cheapest edge that connects the current tree to a vertex not yet in the tree, and add that vertex. This is very similar to how Dijkstra's algorithm works — the difference is that Dijkstra tracks the total distance from the source, while Prim tracks just the weight of the single edge connecting each vertex to the tree. Using a binary min-heap as a priority queue, Prim's runs in O((V+E) log V). For dense graphs with an adjacency matrix, a simpler O(V²) implementation (without a heap) is often used.

The cut property is the mathematical foundation that proves both Kruskal's and Prim's algorithms are correct. A 'cut' is any way of dividing the graph's vertices into two non-empty groups (S and V-S). 'Crossing edges' are edges with one endpoint in each group. The cut property states: the lightest crossing edge for any cut must be part of every MST. Why? If we had an MST that did not include this lightest crossing edge, we could swap it in for a heavier crossing edge (which must exist since the MST spans all vertices) and get a cheaper tree — contradicting the assumption it was minimum. Both Kruskal's and Prim's greedily pick edges that are the lightest crossing some cut, which is why they produce correct MSTs.