Kruskal's algorithm

Sort edges, add the lightest that does not form a cycle using union-find. Edge-centric, O(E lg V).

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:

Put every vertex in its own singleton set (MAKE-SET), and set $A = \emptyset$ .
Sort all edges by non-decreasing weight.
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 α (V))$ total, where $α$ is the inverse-Ackermann function ( $\leq 4$ for any conceivable input). So the sort dominates: $O (E l g E) = O (E l g V)$ overall (since $l g E < l g V^{2} = 2 l g 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.

Kruskal part-way through the scan, on vertices 0, 1, 2, 6, 7, 8 of the exercise graph. Sorted order is 1, 2, 4, 6, 7, 8, 8, 11; the first three each join two different components, so all three are kept. A is a forest, not yet a tree.

The scan finished. 6–8 (6) merges the last two components; 7–8 (7) is then rejected because FIND-SET(7) = FIND-SET(8) — accepting it would close the cycle 6–7–8–6. 0–7 (8) attaches the final piece, giving 5 = |V|−1 edges of total weight 21. Edges 1–2 and 1–7 are never needed.