12. Greedy Algorithms: Minimum Spanning Tree

What this lecture covers

The lecture answers how to find a minimum-weight spanning tree of a weighted, undirected, connected graph, and why a greedy strategy (rather than full dynamic programming) can solve it efficiently. It follows the all-pairs shortest paths lecture and continues the course's study of greedy algorithms, first introduced in lecture one.

By the end, you can state the minimum spanning tree (MST) problem, explain why brute-force search over spanning trees is exponential, prove the optimal-substructure and greedy-choice properties for MST using edge contraction and cut-and-paste arguments, and implement and justify both Prim's algorithm and Kruskal's algorithm.

Key ideas

• Spanning tree: a subset of a graph's edges that is acyclic, connected, and touches every vertex; a minimum spanning tree (MST) minimizes the sum of edge weights among all spanning trees.
• Brute force is exponential: the number of spanning trees can be exponential in the number of vertices (shown with a complete bipartite graph), so trying all of them is not viable.
• Optimal substructure via edge contraction: if an edge e is known to be in some MST, contracting e (merging its endpoints, keeping the lighter of any duplicate edges) and solving the smaller problem, then adding e back, yields an MST of the original graph.
• Greedy choice property (cut lemma): for any partition of the vertices into a set S and its complement, the minimum-weight edge crossing that cut is guaranteed to belong to some MST; this is proved with a cut-and-paste argument.
• Cut-and-paste proofs: the standard technique for proving a greedy algorithm correct — assume an optimal solution lacking the desired edge, swap in that edge for another crossing edge, and show the result is still optimal.
• Prim's algorithm: grows a single set S one vertex at a time, always adding the minimum-weight edge leaving S, using a priority queue keyed by the minimum crossing edge weight; runtime matches Dijkstra's, V log V + E with a Fibonacci heap.
• Kruskal's algorithm: sorts all edges by weight and adds each edge if its endpoints are in different components, tracked with a union-find (disjoint-set) data structure; runtime is dominated by the sort, E log V, or linear with integer weights via radix sort.
• Union-find: the disjoint-set data structure (make-set, union, find-set) that Kruskal's algorithm uses to test whether adding an edge would create a cycle.

Walkthrough

Greedy algorithms recap and the MST problem (0:00)

The lecture reintroduces greedy algorithms as strategies that make locally best choices, contrasted with dynamic programming's guess-and-recurse approach. It then defines a spanning tree (a connected, acyclic subgraph touching every vertex) and the minimum spanning tree problem: find the spanning tree of minimum total edge weight in a weighted, undirected, connected graph.

Why brute force fails, and setting up edge contraction (4:08)

Trying every spanning tree is shown to be exponential using a complete bipartite graph example with 2^n spanning trees. The lecture then sketches a dynamic-programming-style approach: guess an edge known to be in the MST, and simplify the graph around it.

Edge contraction and optimal substructure (15:39)

Contracting an edge e = (u,v) means merging u and v into a single vertex, removing e, and keeping only the lighter of any resulting duplicate edges. The lecture proves that if e belongs to some MST of the original graph G, then an MST of the contracted graph G/e, plus e added back, is an MST of G. Turning this into an algorithm that guesses which edge to contract at each step is still exponential, since there's no structure to exploit in the guess — but it sets up the idea of choosing the edge correctly instead of guessing.

The cut lemma and greedy choice property (29:13)

For any cut of the vertices into S and its complement, the lecture proves that the minimum-weight edge crossing the cut is guaranteed to be in some MST. The proof is a cut-and-paste argument: starting from an arbitrary MST that doesn't contain the target edge e, it identifies the edge e' that crosses the same cut on the unique path between e's endpoints, swaps e' for e, and shows the result is still a spanning tree with weight no greater than the original — hence also minimum. This lemma is the tool that lets both algorithms choose edges without guessing.

Prim's algorithm (42:36)

Prim's algorithm starts with a single vertex as the set S and repeatedly adds the minimum-weight edge leaving S, growing S by one vertex at a time. It's implemented with a priority queue where each vertex outside S is keyed by the minimum weight of an edge connecting it to S, updated via decrease-key operations exactly as in Dijkstra's algorithm. The lecture works a full numeric example on a small graph, then proves correctness by showing the tree built within S is always contained in some MST, using induction and the greedy choice property. Running time matches Dijkstra's: V log V + E with a Fibonacci heap.

Kruskal's algorithm (1:06:41)

Kruskal's algorithm sorts all edges by increasing weight and processes them in order, adding an edge to the growing forest only if its endpoints lie in different connected components — checked and updated using a union-find data structure (make-set, find-set, union). The lecture notes union-find was invented specifically to make this algorithm fast, and that with near-constant amortized union-find operations, the running time is dominated by the sort: E log V in general, or linear time if weights are small integers and radix sort applies. Correctness again follows from the greedy choice property, choosing the cut to be one endpoint's connected component versus everything else, and arguing by induction that every edge added is a safe edge.

Before you watch

• Be comfortable with graph terminology: trees, spanning subgraphs, connected components, and cuts.
• Review Dijkstra's algorithm and its use of a priority queue with decrease-key, since Prim's algorithm follows the same pattern.
• Familiarity with the union-find (disjoint-set) data structure is useful, though the lecture reviews the operations it needs.

Check your understanding

1. Why does contracting an edge known to be in the MST reduce the problem correctly, and why does turning this into an algorithm by guessing the edge still take exponential time?
2. State the cut lemma (greedy choice property) for minimum spanning trees, and sketch how the cut-and-paste argument proves it.
3. In Prim's algorithm, what invariant is maintained about the tree built so far, and how does the induction step use the greedy choice property to extend it?
4. Why does Kruskal's algorithm need union-find rather than simply checking each edge against the tree built so far, and what determines whether its running time is E log V or linear?