Kruskal's algorithm

Kruskal: greedy connected components

Kruskal's algorithm is *edge-centric*: it processes edges globally, from lightest to heaviest, and keeps each one that joins two so-far-separate pieces of the graph. Concretely:

1. Put every vertex in its own singleton set (MAKE-SET), and set $A=\varnothing$.
2. Sort all edges by non-decreasing weight.
3. Scan the sorted edges. For edge $(u,v)$: if FIND-SET(u) != FIND-SET(v) (the endpoints are in different components), add $(u,v)$ to $A$ and UNION(u,v).

The disjoint-set forest (union by rank + path compression) makes the FIND/UNION test almost free — $O(E\,\alpha(V))$ total, where $\alpha$ is the inverse-Ackermann function ($\le 4$ for any conceivable input). So the sort dominates: $O(E\lg E)=O(E\lg V)$ overall (since $\lg E < \lg V^2 = 2\lg V$).

Why it is correct

When Kruskal considers $(u,v)$ with $u$ in component $C_1$, the cut $(C_1, V-C_1)$ respects $A$ (every $A$-edge lies *inside* a component). Because edges are processed in sorted order, $(u,v)$ is the lightest unprocessed edge crossing that cut — a *light edge*. By Corollary 21.2 it is safe. The FIND-SET(u) == FIND-SET(v) rejection is exactly the cycle check: same component means adding the edge would close a cycle.

Worked example

On the CLRS Fig 21.4 graph (9 vertices, 14 edges) the lightest safe edges are taken in order — weights 1, 2, 2, 4, 4, 7, 8, 9 — for a total MST weight of 37. The implementation below reuses the union-find structure from the data-structures module.