Chapter 21: Minimum Spanning Trees: Kruskal and Prim Algorithms

The theoretical foundation rests on the concept of safe edges: a greedy MST algorithm builds its solution one edge at a time, and Theorem 21.1 guarantees that a light edge — the minimum weight edge crossing any cut (S, V\S) that respects the current partial solution — is always safe to add without violating the MST property. Kruskal's algorithm implements this by sorting all edges in increasing weight order and processing them one by one, using a disjoint-set forest to track connected components and adding each edge only when it connects two distinct components via FIND-SET and UNION — running in O(E log V) time dominated by sorting and disjoint-set operations. Prim's algorithm takes a different approach, growing the MST outward from a single root vertex by maintaining a min-priority queue of all vertices not yet in the tree, where each vertex's key stores the minimum weight edge connecting it to the current tree, and repeatedly extracting the minimum-key vertex while updating neighbors via DECREASE-KEY — achieving O(E log V) with a binary heap and the superior O(E + V log V) with a Fibonacci heap. The chapter also surveys advanced topics including the second-best MST, the MST-REDUCE technique for contracting sparse graphs to achieve O(E log log V) performance in Prim's algorithm, and the bottleneck spanning tree problem, which minimizes the maximum edge weight in the tree rather than the total.