MST — Kruskal's Algorithm
MST — Kruskal's Algorithm: build a minimum spanning tree by taking edges cheapest-first, skipping any that would close a cycle.
- 1 <= V <= 10⁵
- V-1 <= E <= 10⁵
- 1 <= weight <= 10⁶
- Needs union-find to reject edges that would close a cycle
Intuition
MST Kruskal's algorithm builds a minimum spanning tree by taking edges in increasing weight order, skipping any that would close a cycle. The greedy rule is short enough to state in a sentence, and its correctness rests on a clean property.
What distinguishes Kruskal from Prim is the shape of the partial result. Prim grows one connected tree outward from a start vertex. Kruskal maintains a forest of separate trees that gradually merge — the cheapest edge in the graph is taken first, wherever it happens to be, so early edges are scattered.
That raises the only hard question in the algorithm: given two vertices, are they already connected through edges taken so far? Answering it by traversal would be O(V) per edge and would dominate the runtime.
- Union-Find answers exactly that question in near-constant time.
Two vertices with the same representative are already in one tree, so an edge between them would form a cycle and is skipped. Otherwise the edge joins two distinct trees and is taken, merging them.
Why taking the cheapest safe edge is optimal is the cut property: for any partition of the vertices, the lightest edge crossing it belongs to some minimum spanning tree. Each edge Kruskal accepts is the lightest crossing the cut between its two components, so no accepted edge can be a mistake.
Stop after V − 1 edges. Finishing with fewer means the graph was disconnected and no spanning tree exists.
Sort edges cheapest-first and take any that doesn't close a cycle — the classic greedy, with union-find providing the cycle test in near-constant time. The pairing is what matters: Kruskal is a sort plus a disjoint-set structure, and the DSU is what makes "would this create a cycle?" cheap enough for the greedy to be practical.
Approach
Before reading on: price up what sorting first costs here, then ask whether you are really just merging groups and asking what connects. Aim for O(E log E) time and O(V) space.
Sort every edge by weight
Process edges cheapest first. This sort is the greedy order and dominates the runtime at O(E log E) — everything after it is nearly linear thanks to Union-Find.
Use Union-Find as the cycle test
Two vertices with the same representative are already connected, so the edge would create a cycle — skip it. Otherwise union them and take the edge. A traversal-based check would be O(V) per edge and would make the algorithm quadratic.
Apply both Union-Find optimisations
Path compression flattens the tree on each find, and union by rank or size keeps merges shallow. Together they give near-constant amortised cost; omitting them degrades the structure to a linked list and the whole algorithm with it.
Understand why greedy is safe
By the cut property, the lightest edge crossing any partition of the vertices belongs to some MST. Each accepted edge is the lightest crossing the cut between its two components at that moment, so no accepted edge can be wrong.
Stop at V − 1 edges
A spanning tree on V vertices has exactly V - 1 edges, so the loop can exit early once that many are taken. Ending with fewer means the graph is disconnected and no spanning tree exists — worth reporting rather than returning a partial forest.
Compare with Prim's algorithm
Prim grows a single tree and suits dense graphs with an adjacency matrix at O(V²). Kruskal sorts all edges and suits sparse graphs at O(E log E). Choosing between them is a question about edge density, not correctness.
Solution & live demo
Common pitfalls
Comparing vertices instead of their roots
if u == v: continue
ru, rv = find(u), find(v) if ru == rv: continue
Two different vertices can already sit in the same component through earlier edges, and adding another edge between them closes a cycle. Only the component representatives reveal that — the raw endpoints never match.
Merging vertices rather than roots
parent[u] = v
parent[ru] = rv
Attaching a non-root breaks the forest: the old root of u's component still points elsewhere, so the two components never actually merge and later cycle tests give wrong answers.
Assuming an MST always exists
return total
return total if used == n - 1 else None
A disconnected graph has no spanning tree — the loop simply runs out of edges having used fewer than n - 1. Returning the accumulated weight reports a spanning forest as though it were a tree.
Edge cases
Fewer than V−1 edges are taken — report no MST.
Any consistent tie-break works; different MSTs may result, all of equal weight.
Endpoints share a root immediately — always skipped.