Kruskal

The problem it solves

Connect every node with the cheapest possible total wiring. Villages and cable, servers and fibre, points and cluster-links — the minimum spanning tree is infrastructure’s favourite abstraction, and it is one of the rare optimisation problems where the greedy answer is provably perfect. Kruskal’s version of the greed is global and almost insolently simple: sort all edges by weight, walk them lightest-first, and accept each edge unless it would close a cycle. When V−1 edges have been accepted, stop — the tree is finished and it is minimal.

Two things make this worth studying beyond the algorithm itself. First, the correctness argument — the cut property — is the exchange argument in its purest form, the template for proving greedy algorithms right everywhere else. Second, the “would this close a cycle?” question is answered by union-find, making Kruskal the canonical demonstration of why that data structure exists: E dynamic connectivity queries, each answered in effectively constant time. The same loop with an early stop is also single-linkage clustering — stop at k components instead of one and you have grouped your data.

The intuition — and where it breaks down

Think of the nodes as islands and edges as bridge proposals, priced. Kruskal is an auditor going through proposals cheapest-first: a bridge between two disconnected islands is approved on the spot — there is no cheaper way those two land-masses will ever meet, since all cheaper proposals have been seen already. A bridge between already-connected islands is waste by definition — a route exists, and this proposal costs at least as much as everything approved so far.

The picture explains the algorithm’s oddest visual: unlike Prim’s single growing blob, Kruskal’s tree assembles as scattered fragments that fuse. The lightest edges may live in far corners of the graph; acceptance order follows price, not geography. The player shows exactly this — inked fragments appearing anywhere, merging late.

Where the intuition needs sharpening: “already connected” sounds cheap to check and is not. The components change with every acceptance, so this is dynamic connectivity — re-running a DFS per proposal costs O(E·V) and turns an elegant algorithm into a slow one. Union-find is the missing piece: each island-group keeps an elected representative; two nodes are connected exactly when their representatives match; approval merges two groups by re-pointing one representative at the other. With path compression and union by rank, each query is amortised near-constant — the inverse-Ackermann bound that interviewers love saying aloud.

Loading…

A walkthrough you can check

Nodes {A, B, C, D}, edges AB=1, CD=2, BC=3, AC=4, BD=5.

1. AB (1): A and B are separate — accept. Components: {A,B}, {C}, {D}.
2. CD (2): separate — accept. Components: {A,B}, {C,D}.
3. BC (3): find(B) = the {A,B} representative, find(C) = the {C,D} one — different. Accept. One component; the tree has V−1 = 3 edges.
4. AC (4), BD (5): never examined — the early exit fired. Had we looked, both would be rejected: their ends are already connected, and each is pricier than everything accepted.

Total weight 6, and no other spanning tree does better (try any swap: removing an accepted edge and adding a rejected one raises the total — that “try any swap” instinct is the exchange argument about to be formalised). The player’s prediction prompts ask precisely these calls: whether the first edge is safe, and whether a given edge’s ends are already connected — questions the inked fragments let you answer by looking.

The invariant

Two, jointly inductive. The accepted set never contains a cycle — enforced directly, since an edge is only accepted when its ends lie in different components. The accepted set is always a subset of some minimum spanning tree — the cut property does the work: when edge e = (u, v) is accepted, consider the cut separating u’s component from everything else. e crosses that cut, and because edges are examined in weight order, e is a lightest crossing edge. The exchange argument finishes it: take any MST; if it lacks e, adding e creates a cycle, which must re-cross the cut somewhere at weight ≥ e’s; swap that edge out for e and the tree is no heavier. So an MST containing all accepted edges always exists.

Run the induction to termination and the accepted set is an acyclic, spanning, MST-subset with V−1 edges — which is to say, an MST. Note what made the proof easy: sorting first turned “lightest crossing edge” from a search problem into a free consequence of the iteration order.

Complexity, derived

The sort dominates: O(E log E) — equivalently O(E log V), since E ≤ V². The main loop performs at most 2E finds and V−1 unions; with path compression and union by rank the total is O(E · α(V)), where α is inverse Ackermann — below 5 for any input that fits in this universe, so effectively linear and invisible next to the sort. Space: O(V) for the union-find forest.

The early exit at V−1 accepted edges matters more than it looks: on dense graphs, most edges are never examined at all once the tree completes. And when the edges arrive pre-sorted — or can be bucketed by integer weight — the sort disappears and Kruskal runs in near-linear time, which is the setting (edge lists on disk, streaming) where it beats Prim decisively.

Disconnected input needs no special case: the loop simply runs out of acceptable edges, producing the minimum spanning forest, one tree per component — the player’s components preset shows this ending honestly.

What people get wrong

• DFS per cycle-check: correct and O(E·V) — the answer that makes interviewers ask “can you do better?” until union-find appears.
• Union-find without compression or rank: degrades toward O(E·V) on adversarial chains; the two one-line optimisations are the whole point of the structure.
• Forgetting the early exit, then scanning a dense graph’s remaining edges for nothing.
• Assuming the MST is unique: with tied weights, different valid MSTs exist. Their totals are provably equal — the safe claim in tests and interviews — but edge sets can differ, so never assert set-equality against another implementation.
• Mixing directions: MSTs are an undirected concept. Feeding directed edges without symmetrising them produces a plausible-looking wrong answer.

Implementation notes

Three components, each small: a sort (edges.sort by weight), a union-find (two arrays — parent and rank — plus find-with-compression and union-by-rank; ten lines total), and the loop with the early exit. Resist the urge to be clever anywhere; the algorithm’s virtue is that nothing in it is subtle except the proof.

For clustering, run the identical loop but stop when the component count reaches k: the result is single-linkage clustering, and the weight of the next-rejected edge is the “gap” between clusters — a number worth reporting. For maze generation, run Kruskal on the grid’s walls with random weights: the accepted edges knock down exactly the walls that make a perfect maze (fully connected, no loops) — the same algorithm wearing a costume.

Ties and determinism: when equal weights exist, the sort’s tie-break decides which MST you get. Tests comparing against another algorithm should compare total weight (invariant across MSTs) rather than edge sets — the unit suite here does exactly that, refereeing Kruskal’s total against Prim’s on shared inputs.

The follow-up questions

Why is the lightest non-cycle edge always safe? The cut property: it is the lightest edge crossing the cut around its component, and the exchange argument shows some MST contains the lightest crossing edge of any cut. Greed with a proof.

Where does union-find earn its keep? E connectivity queries against components that change under V−1 merges. Union-find answers each in amortised α(V); any per-query search pays the component size instead.

Kruskal or Prim? Edge list (possibly on disk or pre-sorted), sparse graph, clustering use-case: Kruskal. Adjacency lists, dense graph, a heap already in hand: Prim at O(E log V). Same total weight either way — all MSTs weigh the same.

How does this become clustering? Stop at k components. Single-linkage clustering is Kruskal’s prefix; the merge distances are the accepted weights, and the dendrogram is the acceptance order.