In the previous lesson we learned to move around Rutalia's network at minimum cost. This lesson poses a different problem that sounds similar and gets confused with it constantly: we don't want to go from one place to another, we want to connect everything while spending the least. Rutalia is going to deploy a network of smart lockers across the city's 9 zones, linked by fiber optic laid along the streets: which segments should be cabled so that all the lockers are connected at the lowest total construction cost? The answer is the minimum spanning tree (MST), and it brings two gifts: the second seed of 01-04 — the union-find that powers Kruskal — and a deep lesson about greedy algorithms: here, unlike the counterexamples of 02-02, greed is provably optimal.

1. Spanning trees: definition and why the minimum matters
2. The cut property: why greedy DOES win here
3. Kruskal: sort the edges and cash in the union-find seed
4. Prim: grow the tree with a heap
5. Kruskal vs Prim: table and selection criteria
6. MST vs shortest paths: Dijkstra's tree is NOT the MST

A spanning tree of a connected graph G = (V, E) is a subset of edges that connects all vertices and contains no cycles. Like every tree, it has exactly n − 1 edges: not one more (there would be a cycle) nor one fewer (something would be left dangling). A graph generally has a huge number of spanning trees; the minimum spanning tree (MST) is the one with the smallest total weight.

Why a "tree"? Think of the lockers' fiber: if the cabling formed a cycle, you could remove any edge of the cycle and everything would stay connected — you would have paid for a useless trench. The optimal solution to a pure connection problem never contains cycles, hence it is a tree.

For the locker network we reuse the canonical graph of 03-01, reinterpreting the weights: where we used to read "van minutes", we now read "construction cost in thousands of euros" (proportional to the segment's length, so the same numbers work). The question: which 8 of the 15 segments get cabled?

Applications of the same pattern, beyond fiber: power and water networks, circuit design, data clustering (the hierarchical clustering of 05-05 has an MST hidden inside), and TSP approximations (the famous 2-approximation is built by walking around an MST).

In 02-02 we watched greedy algorithms crash: the TSP's "nearest neighbor" gave 43.1 km against the optimum of 35.22, and the value/weight knapsack heuristic failed on three-item counterexamples. The honest question is: why should picking "the cheapest edge" work here? The answer has a name of its own:

Cut property. Split the vertices into two non-empty groups (S, V∖S) — a cut. Among all the edges crossing the cut, let e be the one of minimum weight (assume distinct weights for simplicity). Then e belongs to every MST.

Proof by exchange (the classic technique for justifying greedy algorithms): suppose a spanning tree T does not contain e = {u, v}. Since T connects u with v, it contains a path between them, and that path crosses the cut through at least one edge f (≠ e, and by e's definition: weight(f) > weight(e)). Remove f and add e: the result T′ still connects everything (e re-splices the two halves that removing f separated), still has n−1 edges, and weighs less than T. Hence T was not minimum. ∎

The general moral, worth its weight in gold: greedy is neither trustworthy nor suspect by default; it is correct exactly when the problem has an exchange structure that guarantees it. The MST has it (mathematicians say that cycle-free edge sets form a matroid); the TSP and the 0/1 knapsack do not. Dijkstra (03-03) was the other certified greedy: its invariant was also an exchange argument in disguise.

Both algorithms in this lesson are direct applications of the cut property; only the cuts they look at differ.

Kruskal's strategy: scan the edges from cheapest to most expensive, accepting each one unless it forms a cycle with those already accepted. The cut property backs it up: when an edge {u, v} is accepted, it is the cheapest one crossing the cut "u's component versus the rest" (all cheaper edges were already processed and did not separate those halves).

And how is "forms a cycle" detected efficiently? An edge forms a cycle if its two endpoints are already in the same component. In other words: we need component membership with edges arriving one at a time — exactly the case that in 03-02 we said BFS handles poorly and union-find handles beautifully. The seed of 01-04, cashed in:

Full trace on the locker network — the algorithm's "video":

Total construction cost: €37,000, versus the €87,000 it would cost to cable all 15 segments. Notice what Kruskal rejects: precisely the "redundant" edges that would close rings — including the ALM–CEN avenue at 12, which never even gets examined.

Complexity: sorting dominates, O(m log m) = O(m log n); the 2m union-find operations cost O(m · α(n)) — that α, the inverse Ackermann function we met in 01-04, is ≤ 4 for any graph in the physical world. In practice: "sort + almost free".

Prim applies the same cut property with a different tactic: maintain a single growing tree from a starting node, adding at each step the cheapest edge leaving the tree towards the outside (the cut is always "current tree versus the rest"). And who delivers "the cheapest frontier edge"? Once again the heap of 01-04 — the same engine as Dijkstra, with one crucial difference in the priority:

Compare mentally with the Dijkstra of 03-03: same skeleton (heap, settled set, lazy deletion), but the heap tuple carries edge_weight instead of accumulated_distance. That single change turns "being close to the source" into "being close to the tree". Once again the big family: queue→BFS, stack→DFS, heap by distance→Dijkstra, heap by edge→Prim.

Complexity with a binary heap: each edge enters the heap at most once ⇒ O(m log n), like Kruskal. With an adjacency matrix and no heap there is an O(n²) variant which, in dense graphs (m ≈ n²), is in fact better.

For the locker network (sparse: 15 edges, 9 nodes) both are instantaneous and identical in result; at city scale, Kruskal is usually the most convenient on sparse road graphs, and O(n²) Prim wins on dense "all-pairs distance matrix" graphs. If all weights are distinct, the MST is unique and both return exactly the same tree; with ties they may differ in edges, never in total cost.

Dijkstra also produces a tree (the parent tree, with n−1 edges). It is tempting to believe that tree is the MST: it is not, and confusing them is an expensive design error. They optimize different things:

• Dijkstra's tree from s: minimizes the distance from s to each node. It serves the courier leaving the warehouse.
• MST: minimizes the total sum of the chosen edges. It serves whoever pays for the fiber trenches.

Minimal counterexample, three zones:

• MST: {A–B, B–C}, total cost 2 (it discards the 1.5 edge).
• Dijkstra's tree from A: to reach C the direct edge is better (1.5 < 1+1), so {A–B, A–C}, total cost 2.5.

Neither one is "wrong": in the MST, going from A to C costs 2 (detouring through B) even though the network as a whole is cheaper; in Dijkstra's tree, C sits at 1.5 but the total infrastructure is more expensive. And in Rutalia's network the difference is scandalous: Dijkstra's tree from ALM weighs 46 (it uses ALM–EST 7, MER–UNI 6, RIO–PAR 8, EST–IND 9), while the MST weighs 37 (it prefers EST–UNI 3, UNI–HOS 5, IND–HOS 6, PAR–HOS 7). 24% more expensive for optimizing the wrong metric.

• Using Dijkstra's tree as an infrastructure network (or the MST as a routing table): the three-node counterexample should be enough; in Rutalia the confusion costs 24% in overruns or absurd routes. First decide what is being minimized, then pick the algorithm.
• Detecting cycles in Kruskal with BFS/DFS over the accepted edges: correct but O(n) per edge ⇒ O(n·m) total. Union-find brings it down to α(n) per query; that is what we planted it for in 01-04.
• Skipping path compression or union by rank: the union-find degenerates into lists and find becomes O(n). They are four lines; always write them.
• Not stopping at n−1 edges in Kruskal: the result is still correct (everything else would be rejected), but expensive edges get processed uselessly. The break is free.
• Applying MST to a disconnected graph: no spanning tree exists; Kruskal silently returns a minimum spanning forest. Check len(mst) == n - 1 at the end and decide what the shortfall means in your problem (in Rutalia: zones without fiber).
• Tip: when a greedy approach tempts you, look for the exchange argument ("if the optimal solution did not use my choice, I swap it in and nothing gets worse"). If you find it, you have both an algorithm and a proof; if it doesn't materialize, be suspicious — remember the TSP's nearest neighbor.

1. The missing fiber. The city council forbids digging up the UNI–HOS segment (cost 5). Recompute the MST with Kruskal without that edge. How much does the ban add to the cost? Which edge comes in as a replacement, and why that one, in light of the cut property?
2. A safe edge by hand. Without running any algorithm, use the cut property with S = {IND} to prove which edge incident to IND is in every MST of the locker network. Verify against the Kruskal trace.
3. Kruskal as a clusterer. If you stop Kruskal when exactly 3 components remain, you get a partition of the zones into 3 "naturally close" groups (that is how single-linkage clustering works, which will reappear in 05-05). Modify kruskal to accept a k_components parameter and compute the 3 groups of the locker network.

Exercise 1:

MER–UNI (6) comes in instead of UNI–HOS (5). Explanation by cut: once UNI–HOS is removed, at the moment Kruskal holds the fragments {ALM,RIO,MER,CEN,HOS} and {EST,UNI}, the edges crossing that cut are MER–UNI (6), RIO–CEN… no — RIO and CEN sit on the same side; the crossers are MER–UNI (6), UNI–CEN (8) and ALM–EST (7): the minimum available becomes MER–UNI, and the cut property makes it mandatory. The MST worsens only by the difference 6 − 5 = 1.

Exercise 2:

With S = {IND}, the edges crossing the cut are all the edges incident to IND: EST–IND (9) and IND–HOS (6). The minimum is IND–HOS (6), so it belongs to every MST — without running anything. The Kruskal trace confirms it (IND–HOS accepted; EST–IND never even considered before the tree completes). This "single-node cut" trick yields one safe edge per vertex for free: each node's cheapest edge is always in the MST (with distinct weights).

Exercise 3:

Each union reduces the number of components by 1 (we start with n = 9); that is why counting accepted edges suffices. The resulting groups are eloquent: the densely connected urban core on one side, and the Industrial Park and West Park — the degree-2 peripheral zones we have been flagging since 03-01 — as satellites. Kruskal doesn't just build networks: it reveals structure.

The MST answers the infrastructure question — connect everything at minimum total cost — and its greedy solution is no stroke of luck: the cut property, proved by exchange, certifies that the cheapest edge of any cut is mandatory. Kruskal exploits it by sorting edges and policing cycles with the union-find of 01-04 (second seed cashed in: both of that lesson's promises are now settled); Prim exploits it by growing a tree with the same heap as Dijkstra but prioritizing the edge's weight, not the accumulated distance. And we have fenced off with a counterexample what the MST is not: Dijkstra's tree optimizes distances from one source, the MST optimizes the sum — confusing them would cost Rutalia 24% in trenches. So far, our edges measured the cost of traversing them. The next lesson gives them a new meaning: capacity — how many packages per hour fit through each street. With that we enter the problems of maximum flow (03-05): what is the maximum delivery throughput between the warehouse and a neighborhood at rush hour, and which bottleneck limits it.