Experiment № 073 · The story
Only If It Joins Strangers
Why I picked it
A few weeks ago I built the travelling salesman as a lesson in why greedy fails — the tour that only ever improves stops dead in a tangle, and you have to allow yourself to get worse to get out. Kruskal's minimum spanning tree, published in 1956 in a paper of about two pages, is the exact opposite lesson, and I wanted the two sitting in the same collection. Sort every possible link by length. Walk the list from shortest to longest. Take a link only if its two ends aren't already connected to each other. That is the entire algorithm, it never reconsiders anything, and the network it leaves behind is provably the cheapest one that reaches every town. No annealing, no backtracking, no second pass. I find that combination — a rule a child could follow, and a guarantee you'd expect to need a search for — genuinely startling every time.
What I enjoy about it
Watching the colours eat each other. Every town starts as its own island with its own hue, and each accepted link merges two islands into one, so the map spends its first seconds as confetti and then, quite suddenly, resolves into four or five territories that stare at each other across the gaps before the long links finally stitch them together. The bookkeeping underneath is a disjoint-set forest, and the only question it ever answers is are these two already relatives? Two other things I put in on purpose. Switch to grow from one town and you get Prim's algorithm — a completely different order of decisions, one spreading blot instead of scattered fragments, arriving at the same total to the kilometre, because both are obeying the same underlying fact: the cheapest link across any divide has to be in the answer. Then switch to any order at all — same union-find, same acceptance rule, sorting removed — and the same sixty towns cost five or six times the cable. The bookkeeping was never doing the work; the sort was.
Something you might take away
Greedy isn't a personality, it's a bet on the shape of the problem, and here the bet is safe for a reason with a name: the cut property. Draw any line through the map, and whatever the cheapest link crossing that line is, no cheapest network can leave it out — so a rule that grabs short links can't paint itself into a corner. Almost nothing else you'll optimise has that structure, which is precisely why it's worth being able to recognise when it does. And then the slider at the bottom: cut the longest few links of the finished tree and what falls apart isn't arbitrary — those are the widest gaps in the whole map, so the pieces are the clusters. That's single-linkage clustering, which people usually meet as a statistics recipe with no obvious relation to laying cable. It's the same tree, read backwards.