Minimum spanning trees: Kruskal

Same MST as Prim, opposite strategy. Sort edges cheapest-first; add each that doesn't make a cycle.

Merge a forest, don't grow a tree

• Start: V separate one-node trees
• Sort all edges by weight
• For each: different trees? add + merge. Same tree? skip (cycle)
• Stop at V−1 edges — the forest is one tree

Watch the forest merge

Node color = which tree it's in. Orange = accepted (colors merge) · dashed red = rejected (cycle). Seven colors coalesce into one → total 15 (same as Prim).

Kruskal's cost is the sort

250K edges: full Kruskal 133ms, but union-find pass alone <2ms. The sort is 98%.

Union-find is (almost) free

• One union per edge; O(α(V)) amortized — α ≤ 4 for any real input
• Path compression + union by rank (from the trees tier)
• Pre-sorted / integer weights → Kruskal drops to ~linear, beats Prim
• Kruskal parallelizes; Prim wins dense adjacency graphs

Takeaway

An algorithm = a strategy (cut property) + a data structure (union-find). The data structure's quality IS the algorithm's cost. Next: strongly connected components — back to DFS, where the tier began.