Minimum Spanning Trees
In short: a minimum spanning tree connects every depot for the least total cost, using exactly n − 1 links and never a ring. Kruskal's builds it by taking quotes cheapest first and skipping any that would close a ring; Prim's grows one tree outward, always crossing its cheapest offer. Both are safe because of the cut property: split the depots any way you like, and the cheapest link crossing that split always belongs to the MST.
Meridian's depots need a private fibre network so that scanners, route boards and loading-bay screens agree with each other. Carriers have quoted for every link they could lay between two depots, and each link carries data both ways. Buying every quote would be wasteful: a message can hop from depot to depot, so all the network needs is some route between every pair of depots. The question is which links to buy so that every depot is reached, for the least total cost.
You met a version of this at the end of the union-find lesson, where Kruskal's algorithm linked Tunebox's offices. This lesson explains why the greedy rule is right, adds a second algorithm that grows the network outward from one depot, and shows what else the same structure answers.
What you're buying is a tree
Look at the cheapest answer and it never contains a ring. If three depots were linked in a triangle, you could drop the dearest of the three links and everything would still be connected, for less. So the cheapest connecting set is a tree that touches every depot, a spanning tree, and for n depots it has exactly n − 1 links. Among all spanning trees, the one with the smallest total is the minimum spanning tree, or MST.
A graph can have an enormous number of spanning trees. A complete graph on just 10 depots has 100 million of them, so trying them all is out. Instead, two greedy algorithms build the MST one link at a time, and both are safe for the same reason.
Kruskal's: cheapest first, skip what closes a ring
Sort every quote by cost. Walk the list and keep a link unless its two depots are already connected by links you've kept. That link would only close a ring. Union-find answers "already connected?" in near-constant time.
Watch it on six depots. Each badge names the group a depot belongs to right now, kept links are marked done, and rejected ones fade:
Kruskal's takes quotes in rising cost and keeps each one that joins two different groups. The badges are the union-find groups.
Every depot starts as its own group. In cost order the quotes run 2, 3, 4, 5, 6, 7, 8, 9, 11, 13. 6 nodes, 10 edges, undirected. central: c, harbor: h, mill: m, north: n, quarry: q, yard: y.
quotes = [["a", "b", 4], ["b", "c", 1], ["a", "c", 2], ["c", "d", 5], ["b", "d", 3]]
parent = {x: x for x in "abcd"}
def find(x):
while parent[x] != x:
x = parent[x]
return x
kept = []
for a, b, cost in sorted(quotes, key=lambda q: q[2]):
if find(a) != find(b):
parent[find(a)] = find(b)
kept.append(cost)
print(kept)Why greedy is safe: the cut property
Greedy algorithms are often wrong, so this one needs an argument. Split the depots into any two sides, however you like. Some links cross the split.
Cut property. The cheapest link crossing any split belongs to the minimum spanning tree (when costs are all different).
Why: suppose an MST left that cheapest crossing link e out. Add e to it and you
get exactly one ring. That ring crosses the split on e and must cross back
somewhere else, on some link f, which costs more than e. Swap f out for e
and you still have a spanning tree, but a cheaper one, which can't be.
Kruskal's is the cut property applied over and over. When it keeps a link joining groups A and B, take the split "A versus everything else". Every cheaper link crossing that split has already been looked at, and would have been kept, so this link is the cheapest across it. The mirror image is the cycle property: the dearest link on any ring is never needed, and that's exactly what "reject if it closes a ring" does.
A bug in the union-find part breaks the whole guarantee. This version compares parents instead of roots:
The square a, b, c, d should cost 1 + 2 + 3 = 6, with a to d at 4 rejected because it closes a ring. This prints 10. Fix the "already connected?" test.
Here is Kruskal's in full, returning the chosen links:
Sorting costs O(E log E) and the union-find work is nearly linear, so Kruskal's is
O(E log E) overall. Space is O(V + E): the parent map holds one entry per
depot and the sorted quote list holds one entry per link.
Prim's: grow one tree outward
Prim's algorithm applies the cut property differently. Start with one depot "inside". The split is always inside versus outside, so repeatedly take the cheapest link crossing it, and pull the depot at its far end inside. A heap holds the offers. When a depot joins, its offers to outside depots go on the heap. Offers to depots that have joined since go stale, and are skipped when they surface:
Both algorithms find the same total, and so does Prim's from any starting depot:
import heapq
near = {"a": [(4, "b"), (1, "c")], "b": [(4, "a"), (2, "c"), (5, "d")],
"c": [(1, "a"), (2, "b"), (8, "d")], "d": [(5, "b"), (8, "c")]}
def prim(start):
inside, total = {start}, 0
heap = list(near[start])
heapq.heapify(heap)
while heap:
cost, d = heapq.heappop(heap)
if d in inside:
continue
inside.add(d)
total += cost
for offer in near[d]:
if offer[1] not in inside:
heapq.heappush(heap, offer)
return total
print(prim("a"), prim("d"))Now drive it yourself. This is Prim's on the six-depot city, with each outside
depot badged by the cheapest offer it has from inside. Change start, or make a
quote cheaper, and watch which link wins:
Your Prim's. The highlighted region only grows across its cheapest crossing link, which is the cut property in motion.
Which one when?
Kruskal's sorts every link, so it costs O(E log E). Prim's with a heap is also O(E log E), and it doesn't need the whole link list up front, only each depot's neighbours. There is also a version of Prim's with a plain array instead of a heap, which scans all V depots for the cheapest offer at each of V steps: O(V²), no matter how many links there are. On a sparse network that's slower. On a very dense one, where almost every pair of depots has a quote, it wins.
For Meridian's 1,000 depots, array Prim costs about 1,000² = 1,000,000 steps. The heap versions cost about E·log₂E, with E = 1,000·d for d quotes per depot:
| quotes per depot d | E·log₂E | cheaper |
|---|---|---|
| 4 | 47,863 | heap |
| 50 | 780,482 | heap |
| 63 | 1,004,413 | array |
| 100 | 1,660,964 | array |
The crossover is around 63 quotes per depot. City networks are sparse, with a handful of roads per junction, so the heap versions are the right default. Dense instances, such as a quote between every pair of warehouses, are where the O(V²) array version is the better tool.
❓ Cross-question: "Is the backbone the fastest route between two depots?" No. An MST minimises the total cost of the network, not the cost of any one route through it. In a triangle with sides 3, 3 and 5, the MST uses the two 3s, so a message between the ends of the 5 travels 6. Cheapest routes are a shortest-paths question, and the answer is a different tree.
Idioms & real-world patterns
Where spanning trees show up
Fibre, pipe and power layouts start from an MST. Network switches run a spanning-tree protocol so that frames don't circle forever through redundant cables. Clustering algorithms build an MST and cut its dearest links, which is the capstone exercise below. The TSP approximation in a later Meridian section starts from an MST too.
The same answer to a different question
The MST also minimises the most expensive single link, called the bottleneck. If you want a connected network whose worst link is as cheap as possible, the MST already is one. The boss exercise asks exactly this, and the answer is a two-line change to Kruskal's.
⚡ Advanced: Borůvka's algorithm
A third algorithm, and the oldest: every group picks its cheapest outgoing link at the same time, all are added, and the groups merge. The number of groups at least halves each round, so there are O(log V) rounds. Because each group chooses independently, it's the one that parallelises well across machines.
Quick practice
quotes = [["p", "q", 2], ["q", "r", 5], ["p", "r", 9]]
parent = {x: x for x in "pqr"}
def find(x):
while parent[x] != x:
x = parent[x]
return x
kept = []
for a, b, cost in sorted(quotes, key=lambda q: q[2]):
if find(a) != find(b):
parent[find(a)] = find(b)
kept.append(cost)
print(kept)The MST of this triangle costs 2 + 1 = 3, but this prints 6. b's stale offer from a (cost 3) gets counted after c already pulled b inside more cheaply. Fix the check.
🎯 Your turn
Write relay_backbone(depots, quotes). Each quote is [a, b, cost], and all costs
are different. Return the cheapest set of links that connects every depot, each
written [a, b, cost] with the two names in alphabetical order, sorted by cost.
Return None if some depot can't be reached, and [] for a single depot.
relay_backbone(["x", "y", "z"], [["z", "x", 5], ["y", "x", 1], ["z", "y", 3]])→[["x", "y", 1], ["y", "z", 3]]relay_backbone(["a", "b", "c", "d"], [["a", "b", 1], ["c", "d", 2]])→None
Hint: Kruskal's with union-find, then check you kept len(depots) - 1 links.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of Meridian is built. ✅