Minimum Spanning Tree (Kruskal)
Medium+100 XPConnect every town with the cheapest total road and no loops by adding edges cheapest-first.
No visualization loaded.
Watch
—
Press Run to begin.
Imagine towns you must connect with roads, and every possible road has a price. You want EVERY town reachable, spending as little as possible, with no wasteful loops. That cheapest connect-everything set of roads is called a Minimum Spanning Tree. Kruskal's recipe is wonderfully simple: line up every possible road from cheapest to priciest, then go down the list and build each road — but ONLY if its two ends aren't already connected. If they are, that road would just make a loop, so you skip it. Stop once every town is joined.
▸What is a 'spanning tree'?
A spanning tree is a set of roads that touches EVERY town (it 'spans' them all) while staying a tree — meaning no cycles/loops. For V towns it always uses exactly V-1 roads: that's the smallest number of roads that can connect everyone. 'Minimum' spanning tree just means: of all the possible spanning trees, the one whose roads add up to the smallest total cost.
▸Why sort the roads by weight (cheapest first)?
Because Kruskal is greedy: at each step it grabs the cheapest road it can still safely use. Taking the cheapest available road that doesn't make a loop is always part of some minimum spanning tree — it can never trap you into a worse total later. Sorting once up front lets us just walk the list in order and greedily take or skip each road.
▸Why skip a road whose two ends are already connected?
If both ends are already in the same connected blob, there's already a path between them — adding this road would just create a CYCLE (a loop). A loop never helps you reach a new town; it only adds cost. A tree by definition has no cycles, so we throw that road away and move to the next cheapest one.
▸How does Union-Find make the 'already connected?' check fast?
Each town has a group leader (a 'root'). Two towns are connected exactly when they share the same leader — that's a quick find(). When we add a road, we MERGE the two groups under one leader with union(). Both operations are nearly O(1) with path-compression and union-by-rank, so checking 'would this road make a cycle?' is almost instant, even on huge graphs.
▸When do we stop?
The moment the tree has V-1 roads — that's exactly enough to connect all V towns with no loops. At that point every town is in one big group, so every remaining road in the sorted list would only form a cycle. We can stop early instead of scanning the rest.
How the work grows
O(E log E) is good — the practical sorting speed. The cost is dominated by sorting the E edges: O(E log E). After that, each edge does a near-constant Union-Find check, so the whole walk is almost linear in E. Memory is just the parent/rank arrays — one slot per town.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.