The Cheapest Network That Still Connects Everyone

Last week the links just existed — the only question was who could reach whom. Tonight every link gets a price tag, and the question becomes the oldest infrastructure problem there is: connect every dot, spend as little as possible. Every ISP laying fiber, every power grid stringing wire, every railroad baron of the 1800s stared at exactly this map. And the punchline of the week: it falls to two greedy strategies that actually work — a rare luxury, as Week 8 taught you — plus one little data structure, union-find, the fastest island-keeper ever built, that makes them almost free.

Session planHow we will spend the two sessions

Section 1Every link gets a price tag

Here is the valley. Eight small towns — named, apparently, by someone who loved trees — and none of them has internet. A survey crew has walked every route where a fiber cable could go and priced each one, in thousands of dollars. Thirteen possible cables. You only need to buy enough of them that every town can reach every other town, possibly through neighbors — a message from Hazel can hop through Grove and Fir on its way to Alder; that's what networks are for. Your job: connect all eight, spend as little as possible.

Two weeks ago this would have smelled like trouble. Week 8's lesson was that greedy — grab whatever looks best right now — usually face-plants on optimization problems, and when it works you owe a reason (the swap test) before you trust it. Week 9's lesson was that when greedy fails, you pay for correctness with a notebook full of receipts. So here's tonight's small miracle, announced up front: this problem is one of the rare luxuries. Not one but two different greedy strategies solve it perfectly, we can see why with one picture (§5), and the only bookkeeping they need is a data structure so fast it's basically free (§6). No receipts. No notebook. Just disciplined grabbing.

Section 2What you're actually buying

Before any strategy, be precise about the product. You're buying a set of cables that connects everyone — and among all such sets, the cheapest. The first useful observation is about waste: suppose your finished network contains a loop — some ring of towns where you could walk cable-to-cable and come back to where you started. Then one cable in that ring is pure waste. Cut it: anyone who used it can go the long way around the ring, so everyone is still connected, and you just saved its price. Do this until no loops remain. Conclusion, before we've computed anything: the cheapest network never contains a loop. Last week loops were a hazard for explorers; this week they're a hole in your budget.

The second observation is a number you can know in advance. Watch what buying a cable actually accomplishes, in last week's language: at the start, the eight towns are eight separate islands. A useful cable merges two islands into one. A useless cable — both ends already on the same island — merges nothing and closes a loop. To get from eight islands down to one takes exactly seven merges. So:

Section 3The bargain hunter: Kruskal's algorithm

Strategy one is what a coupon-clipper would invent. Ignore the map's geography entirely. Write all thirteen prices on a list, sort it cheapest-first, and walk down the list buying everything — with a single scruple:

Run it on the valley. The sorted list reads 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14. The $2 Birch–Cedar: buy. The $3 Cedar–Dell: buy. The $4 Alder–Birch: buy. The $5 Dell–Elm: buy — four cables, $14k spent, and five towns already form one island. Next comes the $6 Alder–Cedar, and it is the night's most instructive moment: six is cheap, the hunter wants it — but Alder and Cedar are already connected, through Birch, by the $4 and $2 cables. Buying the 6 would close a loop: three cables forming a triangle where two suffice. Skip it forever. Same fate for the $7 Birch–Dell. The $8 Elm–Fir: buy. The $9: skip (loop). The $10 Fir–Grove: buy. The $11 and $12: skip, skip. The $13 Grove–Hazel: buy — that's seven cables, all eight towns, done. The $14 never even gets a look.

Total: 2 + 3 + 4 + 5 + 8 + 10 + 13 = $45k. Compare it to the number you wrote down in §1. And here is the claim that should raise a Week 8 eyebrow: this greedy, loop-dodging shopping spree isn't just a network — it is the cheapest network that exists. For this valley I checked the old-fashioned way — a program tried every possible set of seven cables, all 1,716 of them — and nothing connects all eight towns for less than 45. Section 5 gives you the reason it always works, on any map; no brute force required.

One worry is doing all the work in that rule: "are these two towns already connected?" Look closely and you'll recognize it — it is exactly last week's islands question. "Already connected" means "already on the same island of bought cables." Kruskal asks it once per cable on the list, and real maps have millions of cables — so we need the islands question answered not in one BFS sweep per cable, but instantly, thousands of times in a row, while the islands keep merging underneath us. Park that worry; it has a famous answer, and it's §6's whole job.

Section 4The empire builder: Prim's algorithm

Strategy two has the opposite personality. The bargain hunter buys cables all over the map and lets the fragments find each other; the empire builder refuses to own two fragments. Plant your headquarters in any town. Then, over and over:

From Alder: the only frontier cables are the $4 and the $6, so buy the $4 to Birch. Now the frontier offers the $6, $7, and Birch's $2 — buy the $2 to Cedar. (Notice: the empire builder bought the 4 before the 2. It can only buy what touches the empire — the $2 cable was invisible until Birch joined.) Then the $3 to Dell, the $5 to Elm, the $8 to Fir, the $10 to Grove, the $13 to Hazel. Seven cables: 4, 2, 3, 5, 8, 10, 13 — the exact same seven cables as Kruskal, $45k, bought in a different order by a different philosophy.

That's no coincidence, and the lab will let you check it from every possible headquarters. When all the prices are different — as in our valley — there is exactly one cheapest network, and both strategies are forced into it. If some prices tie, the two strategies (or two different starting towns) may buy different cables and end with different-looking networks — but always, provably, with the same total. Ties are why your answer can look different from your neighbor's and you can both be right; the bill is the thing that's unique-ish, not the blueprint.

Now get your hands on it. Three modes: step the bargain hunter, step the empire builder (tap any town first to move the headquarters), or go freehand — tap cables yourself and try to connect all eight towns for less than $45k. People have tried.

Some things to try:

1. Step the bargain hunter and watch the two early refusals: the $6 and the $7 both flash red along with the loop they would have closed. Cheap is not the same as useful.
2. Switch to the empire builder and run it from Alder; then tap Hazel and run it again. The purchase order reverses almost completely — and the total refuses to move. Try every town.
3. Go freehand and beat $45k. When you give up, try to match it — then tap your $6 Alder–Cedar cable (you bought it, didn't you?) and watch what the narrator says about loops.

Section 5Why grabbing is safe here

Week 8 trained you to distrust everything that just happened. The coin counter looked reasonable and face-planted on {1, 3, 4}; the knapsack packer looked professional and bankrupted itself. Why do these two grabbers get to be perfect? The entire reason fits in one picture, and it's Week 8's own weapon — the swap test — finally landing a clean win.

Split the towns into two groups, any way you like — river towns on the left, hill towns on the right; one town versus the other seven; doesn't matter. Now look only at the cables that cross the split, and find the cheapest one:

Say it in sentences. Any network that connects everyone must get from the left group to the right group somehow — so it crosses the split with at least one cable. Suppose the best network crossed only with pricier cables. Then swap: remove one of its crossing cables, add the cheapest crossing cable instead. The two sides are each still internally wired exactly as before, the new cable re-joins them, and the total just went down — which contradicts "best." So the cheapest cable across any split belongs in the cheapest network. That's the entire argument. No formulas; one swap; Week 8 would be proud.

Now watch both strategies through this lens. Every purchase the empire builder makes is the cheapest cable crossing one particular split: empire versus everyone else. Every purchase the bargain hunter makes is the cheapest cable crossing the split its island versus the rest of the map — anything cheaper was already processed, and either got bought (changing the islands) or closed a loop (crossing nothing). Each grab is blessed by the picture above, each grab is final, and no receipts are ever needed. That is what a greedy-safe problem looks like from the inside: not luck — a swap argument that never jams.

Section 6The fastest island-keeper: union-find

Back to the parked worry. Kruskal's one scruple — "are these two towns already on the same island?" — gets asked for every cable on the list. Last week's answer was a BFS sweep, which is fine once, but Kruskal asks it over and over while the islands keep merging. Running a fresh ripple per question is like recounting a country's population by hand every time someone asks. What we want is a clerk who keeps the books: a data structure with exactly two operations — find ("which island is this dot on?") and union ("merge these two islands") — both effectively instant. That clerk is called union-find, and it's built from one disarmingly silly idea:

Notice how lazy union is — and laziness is the design. Merging islands of a thousand dots each doesn't touch a thousand dots; it redraws one arrow, leader to leader. The cost hides in find: if the arrows form a long chain — you report to your manager, who reports to theirs, who reports to theirs — a find walks the whole chain. Unmanaged, chains can grow until find is as slow as the BFS we were escaping. Two one-sentence tricks kill the problem dead:

• Path compression — the shortcut business card. Once a find has walked to the leader, it walks back and repoints everyone it passed straight at the leader — the leader hands out business cards, and nobody walks that chain again; next time it's one hop.
• Union by size — small joins big, never the reverse. When two islands merge, the smaller island's leader reports to the bigger's. The big island's members don't get any farther from their leader, and chains simply never get a chance to grow long.

Here's the office. Tap two dots to merge their islands (watch one leader start reporting to the other); switch to Find and tap any dot to follow its arrows — and watch the business cards go out. The Tangle button builds a bureaucracy with a genuinely deep chain so you can watch one find flatten it:

The thing to feel in your fingers: tap Tangle me, switch to Find, and tap H. Three arrows — H to G to E to A — and two business cards go out (gold arrows). Tap H again: one arrow. That drop, from 3 to 1, done lazily, only on the paths people actually ask about, is the entire reason million-cable Kruskal runs are dominated by the sorting, not the island questions. Keep tapping finds anywhere — the "arrows walked" counter just refuses to grow.

Section 7The whole machine in Python

Assemble the night: the bargain hunter's loop, with the island-keeper answering its one worry. A dozen lines:

def cheapest_network(towns, cables):     # cables: list of (price, a, b)
    leader = {t: t for t in towns}       # every town starts as its own leader

    def find(t):                          # follow the arrows to the leader
        while leader[t] != t:
            t = leader[t]
        return t

    bought = []
    for price, a, b in sorted(cables):   # cheapest first — the whole strategy
        boss_a, boss_b = find(a), find(b)
        if boss_a != boss_b:              # different islands → no loop:
            bought.append((a, b, price))  #   buy the cable,
            leader[boss_b] = boss_a       #   and merge the islands (one arrow)
    return bought                         # N-1 cables if the map was connected

This version leaves out the two tricks so you can see the skeleton; adding path compression and union-by-size is four more lines, and §6 told you what they buy. The cost, in plain words: with L cables, the sort dominates — about L log L steps, the same n log n you've paid for sorting since Week 4 — and after that the entire shopping spree is L nearly-free island questions. The empire builder lands in the same ballpark (its bookkeeping wants the heap from Notes 07: "cheapest frontier cable" is exactly what heaps serve). For the final flourish, check the output length: if the map was connected you get back exactly N − 1 cables; if you get fewer, the map itself was broken into islands, and the machine just told you — for free.

Section 8Quiz yourself

Six questions, same deal as always: commit to an answer before tapping it. Wrong answers re-teach; that's what they're for.

Section 9Before next session