↩ back to Minimum Spanning Trees
Given a connected, weighted, undirected graph, a minimum spanning tree (MST) is the cheapest possible set of edges that still connects every node — a tree (no cycles), touching every vertex, with the smallest total edge weight of any tree that does. Kruskal's algorithm builds one with a strategy simple enough to state in a sentence: sort every edge by weight, cheapest first, and walk the list adding each edge unless it would close a cycle with edges already added. That's the whole algorithm. The only real work is answering "would this edge close a cycle?" fast, for every one of the graph's edges — and that's exactly the question Union-Find was built to answer in near-constant time, which is why the two are usually taught as a pair. It's one of three standard ways to build an MST — Prim's algorithm grows a single tree outward from one node instead of sorting the whole edge list up front, and Borůvka's algorithm takes a third approach again, letting every component pick its own cheapest edge out in simultaneous rounds instead of a single global sort or a single growing frontier.
Seven waypoints on a trail network, with a cost to cut a trail between each pair (elevation gain, roughly). Press Step or Run to walk the sorted edge list, cheapest first: a black-bordered pair of nodes is the edge currently under consideration, an accepted edge turns solid and orange, a rejected edge turns dashed and fades — rejected because Union-Find reports its two endpoints are already in the same set, meaning some earlier, cheaper path already connects them and this edge would only close a loop. The strip below the graph mirrors the same sorted list as chips; the strip below that shows the live partition into connected sets, the same widget the Union-Find page uses for exactly the same idea.
The greedy choice — always take the cheapest edge that doesn't close a cycle — is safe because of what's called the cut property: for any way of splitting the graph's nodes into two non-empty groups, the single cheapest edge crossing that split must belong to some minimum spanning tree. (If it didn't, swapping it in for whatever crossing edge the tree used instead could only make that tree cheaper, contradicting that the tree was already minimum.) Kruskal's sorted-order walk keeps satisfying this property one edge at a time without ever having to think about splits explicitly: when the algorithm accepts an edge, it's always the cheapest one connecting the two sets its endpoints currently belong to, since every cheaper edge either already got processed (and either joined those sets earlier or connected two different sets entirely) or would have been rejected for closing a cycle. Repeat that for every accepted edge and the whole tree ends up minimum, not just each piece of it.
The cycle check is where Union-Find does all the
work: two nodes are in the same set exactly when some earlier accepted edge already connects them
(directly or transitively), so "would this edge close a cycle?" is just connected(a, b),
and "accept it" is just union(a, b). No graph traversal needed on every edge, which is
what would make an MST algorithm built on repeated DFS/BFS reachability checks needlessly slow.
Matches the demo above one for one — same sort, same Union-Find (two-pass path compression + union
by rank, identical to the version on the Union-Find
page), just without the yield points the demo uses to show every intermediate accept and
reject:
function kruskalMST(numNodes, edges) {
// edges: [{ a, b, w }, ...] — undirected, weight w
const sorted = edges.slice().sort((x, y) => x.w - y.w);
const parent = Array.from({ length: numNodes }, (_, i) => i);
const rank = new Array(numNodes).fill(0);
function find(x) {
let root = x;
while (parent[root] !== root) root = parent[root];
while (parent[x] !== root) {
const next = parent[x];
parent[x] = root; // path compression
x = next;
}
return root;
}
const mst = [];
let totalWeight = 0;
for (const edge of sorted) {
const rootA = find(edge.a);
const rootB = find(edge.b);
if (rootA === rootB) continue; // would close a cycle — reject
if (rank[rootA] < rank[rootB]) parent[rootA] = rootB;
else if (rank[rootA] > rank[rootB]) parent[rootB] = rootA;
else { parent[rootB] = rootA; rank[rootA]++; }
mst.push(edge);
totalWeight += edge.w;
if (mst.length === numNodes - 1) break; // spanning tree complete
}
return { mst, totalWeight };
}Ties mean the MST isn't always unique. If two edges share the same weight, which one Kruskal happens to sort first can change which edges end up in the tree — though never the total weight, which is the same across every valid MST for a given graph. The demo's seven waypoints deliberately use ten distinct trail costs so there's exactly one right answer to point at; a real-world graph has no reason to avoid ties, and an implementation that needs one specific tie-broken answer (not just any minimum-weight tree) has to add an explicit tie-break rule on top — same caveat topological sort's Pitfalls section makes about non-unique orderings.
A disconnected graph doesn't get a spanning tree — it gets a spanning forest. If
the input graph has no edges linking two of its pieces, no amount of edge-accepting will ever connect
them, and the algorithm has no way to notice or complain: it just runs out of edges with fewer than
numNodes - 1 accepted, having actually built the minimum spanning tree of each piece
separately. Whether that's the right behavior or a silent bug depends entirely on the caller — worth
checking for explicitly (e.g. mst.length === numNodes - 1) if a single connected tree was
assumed.
The sort is the bottleneck, not the Union-Find calls. See Complexity below — this is why Kruskal is usually described by its sort cost rather than by how cheap the cycle check is.
Union-Find without its own optimizations degrades everything built on top of it.
Skip path compression or union by rank in the find/union calls above and
each one can cost up to O(n) instead of near-constant — see
Union-Find's own Pitfalls for why both
optimizations are needed together, not just one.
Time: O(E log E), dominated entirely by the initial sort — with
E up to O(V²) for a dense graph, log E and log V
differ by at most a constant factor, so this is equally often written O(E log V). The
main loop itself is only O(E · α(V)) — E calls to Union-Find's
near-constant find/union — which would be the whole story if the edges
arrived pre-sorted; in practice the sort is what sets the ceiling.
Space: O(V + E) — O(E) to hold the sorted edge list,
O(V) for Union-Find's parent and rank arrays, same as
Union-Find alone. The
Reverse-Delete algorithm reaches the identical tree by
sorting the same list the opposite direction and testing connectivity instead of components — a real
asymptotic step down to O(E · (V + E)), not just a stylistic variation.
For a decision guide across all ten of this site's Minimum Spanning Trees entries — when to reach for Kruskal's over Prim's or Borůvka's, and when the real question is bottleneck or second-best instead of minimum total — see Choosing a Minimum Spanning Tree Algorithm.