Day 22 — Minimum Spanning Trees
A spanning tree of a connected graph is a subgraph that includes every vertex and is acyclic — a tree. A minimum spanning tree (MST) is the spanning tree with the lowest total edge weight.
That sounds narrow. It isn’t. MSTs show up whenever you want to connect things cheaply: fiber networks, water pipes, electrical grids, road systems, clustering algorithms in machine learning, and image segmentation. The problem is also one of the few optimization problems where a greedy algorithm is provably optimal — and understanding why the greedy works (the cut property) is as important as knowing the code.
What you’ll learn today
- The spanning tree and MST definitions — why cycles are excluded, why all vertices must appear
- The cut property — the mathematical justification for why both greedy MST algorithms are correct
- The cycle property — the dual view: the heaviest edge in any cycle is never in the MST
- Kruskal’s algorithm — sort all edges by weight, add the cheapest that doesn’t form a cycle, powered by Union Find from Day 20
- Prim’s algorithm — grow the MST one vertex at a time using a priority queue from Day 7
- When to use which — Kruskal wins on sparse graphs; Prim wins on dense ones
- Eight interview problems — Min Cost to Connect All Points, Redundant Connection, Network Connected, Remove Max Edges, Most Stones Removed, Accounts Merge, Critical Edges, Swim in Rising Water
The secret that makes MSTs feel magical: both Kruskal’s and Prim’s are greedy algorithms that are provably correct. In most optimization problems, greedy fails — the locally best choice isn’t globally best. MSTs are the exception. The cut property is the proof that “always pick the cheapest safe edge” never leads you astray.
Roadmap
- Introduction — spanning trees, MST definition, the cut and cycle properties, and uniqueness conditions.
- Kruskal’s Algorithm — sort-and-union-find implementation, correctness proof via the cut property, and complexity.
- Prim’s Algorithm — priority-queue growing, lazy vs eager variants, dense-graph O(V²) optimization.
- Advanced Patterns — Borůvka’s, minimum bottleneck spanning trees, second-best MST, and real-world applications.
- Basic Questions — warm-ups: manual Kruskal, Prim step-by-step, union-find from scratch, component counting.
- Practice Questions — eight interview problems covering every MST and union-find technique in the chapter.
MSTs bridge the gap between graph theory and practical algorithms. They share Union Find with Day 20 and priority queues with Day 7 — if either feels shaky, revisit those chapters first.
Coming up: Day 23 — Topological Sort, where directed acyclic graphs replace undirected ones and dependency ordering replaces weight minimization.