Kruskal's Algorithm: Build a Minimum Spanning Tree with Union-Find
Kruskal's algorithm for the minimum spanning tree — sort edges by weight, reject cycles with union-find, add the cheapest safe edge. Code, walkthrough, complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
You have a set of towns and a list of possible roads, each with a build cost. You want every town reachable from every other town, and you want to spend as little as possible. That is the minimum spanning tree problem, and Kruskal's algorithm solves it with one of the cleanest greedy strategies in all of graph theory: sort every edge by cost, then keep the cheapest one that doesn't waste money.
The whole trick is deciding when an edge "wastes money." An edge is useless if both of its endpoints are already connected through cheaper roads you've already bought — adding it would just create a redundant loop. Kruskal's answers that question in near-constant time using a Disjoint Set Union (union-find) structure. Get this pattern down and you also unlock cycle detection, connected-component counting, and a dozen network problems that look unrelated until you see the shape.
The problem
Given n nodes labeled 0 to n-1 and a list of weighted edges [u, v, weight], find a subset of edges that connects all n nodes with the minimum total weight and no cycles. That subset is a spanning tree, and the cheapest one is the minimum spanning tree. A tree over n nodes always has exactly n - 1 edges.
Input: n = 5
edges = [[0,1,2], [0,3,6], [1,2,3], [1,3,8], [1,4,5], [2,4,7], [3,4,9]]
Output: 16
MST edges chosen: (0-1,w2), (1-2,w3), (1-4,w5), (0-3,w6)
2 + 3 + 5 + 6 = 16, using exactly 4 edges for 5 nodesTwo facts drive everything:
- The answer has exactly
n - 1edges. Once you've added that many, you're done. - An edge is safe to add only if its two endpoints live in different connected components. Same component means a cycle.
The brute force baseline
The greedy idea (sort, then add cheap edges) is actually correct on its own. What makes a naive version slow is how you check for a cycle. The obvious way: keep the edges you've accepted so far, and for each new candidate, run a DFS or BFS to see if its endpoints are already linked.
function kruskalNaive(n, edges) {
edges.sort((a, b) => a[2] - b[2]);
const mst = [];
let cost = 0;
const connected = (u, v, chosen) => {
// BFS over edges accepted so far
const adj = Array.from({ length: n }, () => []);
for (const [a, b] of chosen) { adj[a].push(b); adj[b].push(a); }
const seen = new Set([u]);
const queue = [u];
while (queue.length) {
const node = queue.shift();
if (node === v) return true;
for (const nb of adj[node]) if (!seen.has(nb)) { seen.add(nb); queue.push(nb); }
}
return false;
};
for (const [u, v, w] of edges) {
if (!connected(u, v, mst)) { mst.push([u, v]); cost += w; }
}
return cost;
}This is correct but painful. Every candidate edge rebuilds an adjacency list and runs a fresh traversal — O(V + E) work per edge, across up to E edges, so O(E · (V + E)). On a dense graph that's roughly cubic. The cycle check is the bottleneck, and it re-derives connectivity from scratch every single time.
The key insight: track components, don't re-traverse
You don't need to discover whether two nodes are connected — you can remember it. Maintain the current partition of nodes into components, and answer "are u and v connected?" by comparing which component each belongs to.
That is exactly what union-find (Disjoint Set Union) does with two operations:
find(x)returns a representative "root" forx's component. Two nodes are connected iff they share a root.union(x, y)merges the two components into one.
With path compression (flatten the tree during find) and union by rank (attach the shorter tree under the taller one), both operations run in near-constant amortized time — O(α(n)), where α is the inverse Ackermann function, effectively ≤ 4 for any input you'll ever see. The O(E·V) cycle check collapses into an O(1) root comparison, and Kruskal's becomes dominated purely by the initial sort.
The optimal solution
Here is the exact algorithm the visualizer traces: a UnionFind class with rank-based merging, then Kruskal sorting edges and greedily unioning.
class UnionFind {
constructor(n) {
this.parent = new Array(n).fill(0).map((_, i) => i);
this.rank = new Array(n).fill(0);
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // path compression
}
return this.parent[x];
}
union(x, y) {
let rootX = this.find(x);
let rootY = this.find(y);
if (rootX === rootY) return false; // same component -> cycle, reject
if (this.rank[rootX] > this.rank[rootY]) {
this.parent[rootY] = rootX;
} else if (this.rank[rootY] > this.rank[rootX]) {
this.parent[rootX] = rootY;
} else {
this.parent[rootY] = rootX;
this.rank[rootX]++;
}
return true; // merged two components
}
}
function Kruskal(n, edges) {
edges.sort((a, b) => a[2] - b[2]);
let uf = new UnionFind(n);
let mstCost = 0;
for (let [x, y, w] of edges) {
if (uf.union(x, y)) {
mstCost = mstCost + w;
}
}
return mstCost;
}The elegance is that union returns a boolean. When it returns true, the two endpoints were in different components and just got merged — so this edge belongs in the MST and we add its weight. When it returns false, the endpoints already shared a root, the edge would close a cycle, and we skip it silently. Sorting guarantees that among all edges bridging two components, we always reach the cheapest one first.
Walkthrough
Trace n = 5 with the input above. After sorting by weight the edge order is: (0-1,2), (1-2,3), (1-4,5), (0-3,6), (2-4,7), (1-3,8), (3-4,9). The parent array starts as [0,1,2,3,4] (every node its own root).
| Edge (w) | find(x) | find(y) | Same root? | Action | parent after | MST cost |
|---|---|---|---|---|---|---|
| 0-1 (2) | 0 | 1 | no | union → add | [0,0,2,3,4] | 2 |
| 1-2 (3) | 0 | 2 | no | union → add | [0,0,0,3,4] | 5 |
| 1-4 (5) | 0 | 4 | no | union → add | [0,0,0,3,0] | 10 |
| 0-3 (6) | 0 | 3 | no | union → add | [0,0,0,0,0] | 16 |
| 2-4 (7) | 0 | 0 | yes | cycle → skip | [0,0,0,0,0] | 16 |
| 1-3 (8) | 0 | 0 | yes | cycle → skip | [0,0,0,0,0] | 16 |
| 3-4 (9) | 0 | 0 | yes | cycle → skip | [0,0,0,0,0] | 16 |
By the fourth edge every node's root is 0 — all five nodes sit in one component, so the MST already has its n - 1 = 4 edges. The last three edges each find both endpoints rooted at 0, so union returns false and they're rejected as cycles. Final MST cost: 16.
Notice the greedy never backtracks. Edge 0-3 at weight 6 gets accepted even though heavier edges exist, because at that moment node 3 was still isolated and this was the cheapest way to attach it.
Complexity
| Step | Time | Space | Why |
|---|---|---|---|
| Sort edges | O(E log E) | O(log E) | comparison sort over all E edges dominates |
| Union-find (all ops) | O(E · α(n)) | O(n) | 2E finds + up to n−1 unions, each near-constant |
| Total | O(E log E) | O(n) | sorting is the bottleneck; DSU is effectively free |
Since E ≤ n², log E is at most 2 log n, so you'll also see the bound written as O(E log n) — they're the same thing. Space is O(n) for the two DSU arrays plus O(E) if you count the edge list itself. The inverse Ackermann factor α(n) is below 5 for any realistic n, which is why union-find is treated as constant-time in practice.
Common mistakes
- Forgetting to sort first. Kruskal's correctness rests entirely on processing edges cheapest-first. Skip the sort and you get a spanning tree, not the minimum one.
- Calling
finddirectly instead of throughunion. The whole cycle check lives insideunion'srootX === rootYcomparison. If you add the edge without checking that return value, cycles slip in. - Skipping path compression or union by rank. Without them,
findcan degrade to O(n) on a pathological chain, dragging the total toward O(E·n). Both optimizations are one line each — always include them. - Not stopping conceptually at
n - 1edges. The loop above naturally rejects every extra edge as a cycle, so it's harmless here, but for very dense graphs you can break early once the MST hasn - 1edges to skip needlessfindcalls. - Assuming a unique MST. When edges share weights (ties), different valid MSTs can have the same total cost. Your chosen edges may differ from a reference solution while the total weight still matches.
Where this pattern shows up next
Union-find and component-tracking recur across graph problems far beyond MST:
- Redundant Connection — the purest use of union-find: the edge that returns
falsefromunionis the one closing a cycle. - Find if Path Exists in Graph — connectivity reduces to a single
find(source) === find(dest)check. - Max Area of Island — grid components you could count with either DFS or a disjoint set.
- All Paths From Source to Target — a DAG traversal that shows the other side of graph exploration, enumerating routes rather than merging components.
You can also step through Kruskal's algorithm interactively to watch the edge pool sort, the DSU roots merge, and cycle edges get rejected in real time.
FAQ
What is the difference between Kruskal's and Prim's algorithm?
Both build a minimum spanning tree, but they grow it differently. Kruskal's is edge-centric: it sorts all edges globally and adds the cheapest one that connects two separate components, using union-find to detect cycles. Prim's is node-centric: it grows a single connected tree outward from a start node, always adding the cheapest edge leaving the current tree, typically via a priority queue. Kruskal's shines on sparse graphs (few edges), while Prim's with a binary heap can be better on dense graphs.
Why does Kruskal's algorithm need union-find?
Because the core question — "would adding this edge create a cycle?" — is equivalent to "are these two endpoints already in the same connected component?" Union-find answers that in near-constant amortized time via find, and merges components in union. Without it, you'd re-run a DFS or BFS for every candidate edge, turning an O(E log E) algorithm into roughly O(E·V). The disjoint-set structure is what keeps the cycle check cheap.
What is the time complexity of Kruskal's algorithm?
O(E log E), which is dominated by sorting the edges. After sorting, the algorithm does about 2E find operations and up to n−1 union operations, each running in O(α(n)) amortized time thanks to path compression and union by rank. Since the inverse Ackermann function α(n) is effectively a small constant, the union-find work is negligible and the sort is the true bottleneck. Because E ≤ n², this is equivalently written O(E log n).
Does Kruskal's algorithm always produce a unique tree?
Not necessarily. If all edge weights are distinct, the minimum spanning tree is unique. But when several edges share the same weight, there can be multiple valid MSTs — the specific set of edges you pick depends on tie-breaking order during the sort. What is always guaranteed is that the total weight is the minimum possible; only the chosen edges may vary between equally optimal trees.
What happens if the graph is disconnected?
Kruskal's will process every edge and produce a minimum spanning forest — one MST per connected component — rather than a single spanning tree. The number of accepted edges will be n - c, where c is the number of components, instead of n - 1. If your problem requires a single tree spanning all nodes, a component count above one signals that no spanning tree exists, and you should check for that condition explicitly.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.