The cheapest way to connect everything — and two famous greedy algorithms that are really the same algorithm with a different rule for what to grow.
Given a connected undirected graph with edge weights, a spanning tree is an acyclic subset of edges connecting all vertices, and a minimum spanning tree is one of least total weight. Chapter 21 presents a single generic greedy method, proves one theorem that justifies it, and then shows that Kruskal’s and Prim’s algorithms are just two ways of instantiating it. The chapter is the cleanest demonstration in the book of greedy design done properly: prove the safe-choice theorem first, and both algorithms follow.
Input: a connected undirected graph G = (V, E) with a weight function w : E → ℝ. Find an acyclic subset T ⊆ E that connects all vertices and minimises w(T) = ∑(u,v)∈T w(u,v).
Such a T is a tree, and it always has exactly |V| - 1 edges. The motivating picture is a wiring problem: connect n pins with the least total wire.
s minimises the distance from s to each vertex individually. They are usually different trees, and an MST can contain a path between two vertices far longer than their shortest path. Chapter 22 does shortest paths; this chapter does not.Both algorithms grow a set A that is always a subset of some MST, one edge at a time.
GENERIC-MST(G, w)
1 A = ∅
2 while A does not form a spanning tree
3 find an edge (u,v) that is safe for A
4 A = A ∪ {(u,v)}
5 return AThe loop invariant: A is a subset of some minimum spanning tree. An edge is safe for A if adding it keeps that invariant true.
Line 3 is the entire difficulty. The invariant handles correctness: it holds initially (the empty set is in every MST), it is maintained by definition of safe, and at termination A is a spanning tree that is a subset of an MST — hence is an MST.
Three definitions are needed to state the theorem.
| Term | Definition |
|---|---|
Cut (S, V-S) | A partition of the vertices into two non-empty parts. |
| An edge crosses the cut | Its two endpoints are on opposite sides. |
A cut respects a set A | No edge in A crosses it. |
| Light edge | A crossing edge of minimum weight among all edges crossing that cut. |
A. No edge of A crosses the dashed line, and the lightest crossing edge is guaranteed to belong to some MST.A be a subset of some minimum spanning tree of G, let (S, V-S) be any cut that respects A, and let (u,v) be a light edge crossing that cut. Then (u,v) is safe for A.Proof sketch (an exchange argument, as in Chapter 15). Let T be an MST containing A. If (u,v) ∈ T, done. Otherwise adding (u,v) to T creates a cycle, and that cycle must cross the cut an even number of times, so it contains some other crossing edge (x,y). Since the cut respects A, (x,y) ∉ A. Form T′ = T - {(x,y)} ∪ {(u,v)}. Because (u,v) is light, w(u,v) ≤ w(x,y), so w(T′) ≤ w(T) — and T′ is also spanning. So T′ is an MST containing both A and (u,v). □
C is a connected component in the forest Gᵀ = (V, A), and (u,v) is a light edge connecting C to some other component, then (u,v) is safe for A. This is the form both algorithms actually use.A is a forest of many trees. At each step add the globally lightest edge that connects two different trees. The forest merges into one tree at the end.MST-KRUSKAL(G, w)
1 A = ∅
2 for each vertex v ∈ G.V
3 MAKE-SET(v)
4 sort the edges of G.E into non-decreasing order by weight w
5 for each edge (u,v) ∈ G.E, taken in that order
6 if FIND-SET(u) ≠ FIND-SET(v) // different trees: no cycle
7 A = A ∪ {(u,v)}
8 UNION(u, v)
9 return AThe disjoint-set structure from Chapter 19 is exactly the cycle test: two endpoints in the same set means adding the edge would close a cycle.
| Step | Cost |
|---|---|
| Sorting the edges | O(E lg E) — dominates |
O(V) MAKE-SET plus O(E) FIND-SET/UNION | O((V + E) · α(V)), effectively linear |
| Total | O(E lg E) = O(E lg V), since |E| < |V|² |
A is always a single tree, starting from an arbitrary root. At each step add the lightest edge connecting the tree to a vertex outside it. Structurally this is Dijkstra’s algorithm with a different key.MST-PRIM(G, w, r)
1 for each u ∈ G.V
2 u.key = ∞; u.π = NIL
3 r.key = 0
4 Q = G.V // min-priority queue on key
5 while Q ≠ ∅
6 u = EXTRACT-MIN(Q)
7 for each v ∈ G.Adj[u]
8 if v ∈ Q and w(u,v) < v.key
9 v.π = u
10 v.key = w(u,v) // DECREASE-KEYv.key is the weight of the lightest edge connecting v to the tree built so far. The MST is {(v, v.π) : v ∈ V - {r}}.
| Priority queue | EXTRACT-MIN | DECREASE-KEY | Total |
|---|---|---|---|
| Array | O(V) | O(1) | O(V²) |
| Binary min-heap | O(lg V) | O(lg V) | O(E lg V) |
| Fibonacci heap | O(lg V) | O(1) amortized | O(E + V lg V) |
O(1) amortized DECREASE-KEY matters precisely because Prim and Dijkstra call DECREASE-KEY up to |E| times but EXTRACT-MIN only |V| times. The 4th edition removed the Fibonacci heap chapter from print, but the bound is still quoted here and in Chapter 22.| Kruskal | Prim | |
|---|---|---|
| Grows | A forest that merges | A single tree from a root |
| Picks | Globally lightest edge not forming a cycle | Lightest edge leaving the current tree |
| Key structure | Disjoint sets (Ch 19) | Min-priority queue (Ch 6) |
| Time | O(E lg V) | O(E lg V), or O(E + V lg V) with a Fibonacci heap |
| Better on | Sparse graphs, or when edges arrive already sorted | Dense graphs — the array version is O(V²), which beats O(E lg V) when E ≈ V² |
GENERIC-MST with a different rule for finding a safe edge, and both are justified by the same Theorem 21.1. Kruskal applies Corollary 21.2 to the two components an edge would join; Prim applies Theorem 21.1 to the cut separating the tree from everything else.|V| vertices with |V|-1 edges of minimum total weight. It is not the shortest-path tree.GENERIC-MST maintains the invariant “A is a subset of some MST” and repeatedly adds a safe edge.A if no edge of A crosses it. A light edge is a minimum-weight crossing edge.A is safe. Proved by exchange: swap it for the heavier crossing edge on the cycle it creates.O(E lg V).O(E lg V), or O(E + V lg V) with a Fibonacci heap.Chapter 22 keeps the weights but changes the objective to shortest paths from a single source. It introduces relaxation, the technique underneath every shortest-path algorithm, then gives Bellman-Ford for graphs with negative edges, a linear-time DAG algorithm, and Dijkstra — which is Prim’s algorithm with the key changed from edge weight to accumulated distance.