What is Kruskal's algorithm?
Kruskal's algorithm builds a minimum spanning tree — the cheapest set of edges that connects every
node with no cycles — by sorting every edge by weight and walking the sorted list once, greedily adding
each edge unless it would connect two nodes that are already reachable from each other. It leans directly
on union-find: checking "are these two nodes already connected?" is exactly find(a) === find(b),
and accepting an edge is exactly union(a, b).
- Minimum spanning tree
- The cheapest possible set of edges connecting every node, with no cycles
- Greedy edge
- The cheapest edge not yet ruled out — taken immediately, never reconsidered
- Cycle check
find(a) === find(b)— are these two endpoints already in the same set?
Why Kruskal at all?
Picture connecting a handful of towns with roads. You don't plan the whole network up front — you build the cheapest possible road first, then the next cheapest, and so on.
The only rule: skip a road if the two towns it connects can already reach each other some other way — that road would just be a redundant loop. Keep going until every town is reachable, and the roads you built are provably the cheapest network possible.
Cheapest road first. A road that would just loop back to a town you can already reach gets skipped.
What Kruskal actually does
Two moves, in order: sort every edge cheapest-to-priciest once, then walk that list a single time, accepting or rejecting each edge as you go. Neither move is optional — skip the sort and the greedy pick stops being provably safe.
Sort every edge by weight, once
Before any decision gets made, every edge in the whole graph is ranked cheapest to priciest. The rest of the algorithm never re-sorts or looks back — it just walks this list in order.
Input order (top) doesn't matter. Sorted order (bottom) is all Kruskal ever reads from.
Walk the sorted list, accept unless it cycles
One pass, left to right. Every edge is either accepted — it joins the tree — or rejected because its two endpoints are already connected. The pass stops once the tree spans every node.
Once the tree has 3 edges, every remaining road would only create a cycle.
Cycle-checking with Union-Find
This is where union-find does all the work. Every node starts in its own set. "Are these two
endpoints already connected?" is exactly find(a) === find(b) — no traversal needed, just a
lookup. Accepting an edge is exactly union(a, b): it merges their two sets into one.
Different sets → union and accept
B and D sit in different sets so far. find(B) and find(D) return different roots,
which proves no path between them exists yet — adding this edge can't create a cycle.
find(B) ≠ find(D) → union(B, D) → accept. The tree now spans every town.
function tryAddEdge(uf: UnionFind, a: string, b: string): boolean {
const rootA = uf.find(a);
const rootB = uf.find(b);
if (rootA === rootB) {
return false; // same set already — this edge would cycle
}
uf.union(a, b); // merge the two sets into one
return true;
}
Same set already → reject
By the time A–B is considered, A and B are already in the same set — B joined it when B–C was
accepted. find(A) and find(B) return the same root, so this edge is redundant.
find(A) === find(B) → reject. Adding it would only create a cycle inside {A, B, C}.
function wouldCycle(uf: UnionFind, a: string, b: string): boolean {
return uf.find(a) === uf.find(b);
}
// inside the main loop, sorted cheapest to priciest:
for (const edge of sortedEdges) {
if (wouldCycle(uf, edge.a, edge.b)) {
continue; // reject — skip straight to the next edge
}
uf.union(edge.a, edge.b);
mst.push(edge); // accept — this edge joins the tree
}
Where it works — and where it breaks
The greedy pick is only provably safe because every edge is visited in ascending weight order. Skip the sort and the algorithm can still produce a valid, cycle-free tree — just not the cheapest one.
Works when edges are sorted ascending
Taking B–C, then A–C, then (rejecting A–B), then B–D always finds the cheapest edge available at every step. That's what makes the total provably minimal.
Breaks when edges aren't sorted first
Taking A–B, then C–D, then B–C (which happens to connect everything) never creates a cycle — every accepted edge is still valid. But two expensive edges got locked in before cheaper ones were ever compared.