Minimum Spanning Trees and Algorithms

Core Idea

A spanning tree of a connected graph includes all vertices using n−1 edges. A minimum spanning tree (MST) minimizes total edge weight. Kruskal's algorithm greedily adds edges in weight order; Prim's algorithm grows a tree vertex by vertex. Both yield optimal MSTs.

How It's Best Learned

Implement or trace Kruskal's and Prim's algorithms on small weighted graphs. Understand why greedy works (matroid structure). Recognize applications: network design, clustering.

Common Misconceptions

An MST is not necessarily unique (ties in edge weights yield different MSTs with equal cost). There is no single 'right' spanning tree for a given graph unless weights are specified.

Explainer

You already know from your prerequisites that a spanning tree of a connected graph is a subgraph that touches every vertex using exactly n−1 edges and contains no cycles. A minimum spanning tree (MST) is the spanning tree whose edge weights sum to the smallest possible total — the cheapest way to keep the graph connected. Think of designing a road network: you need every city reachable from every other, and you want to minimize total construction cost. The MST solves exactly this problem.

Kruskal's algorithm approaches this greedily: sort all edges from lightest to heaviest, then add each edge to the MST if and only if it doesn't create a cycle. You keep going until you have n−1 edges. The cycle-detection check is the key operation — in practice it's implemented with a Union-Find data structure from your graph theory background. The intuition is: if two vertices are already connected (they're in the same component), adding another edge between them would just create a redundant loop, so skip it.

Prim's algorithm grows the MST differently: start from any vertex, and repeatedly add the cheapest edge that connects the current tree to a vertex not yet in the tree. Think of it as expanding a frontier. At each step you pick the minimum-weight bridge between the "in" and "out" vertices. Both algorithms are correct for the same reason: the cut property, which says that the minimum-weight edge crossing any cut (partition of vertices into two sets) must belong to some MST. This is the deeper structural reason greedy works here — the problem has a matroid structure that guarantees local greedy choices are globally optimal.

The key insight separating MSTs from general optimization: you don't need to consider all possible spanning trees (exponentially many). Greedy is sufficient because the minimum-edge-crossing-a-cut property is universal. This is why MSTs are tractable where other network optimization problems (like minimum Hamiltonian paths) are NP-hard — the cut property gives you a local certificate of global optimality at every step. When you encounter applications like clustering (remove the heaviest edges from an MST to form clusters) or approximation algorithms for TSP, you're leveraging this same structural guarantee.