Minimum Spanning Tree

The cut property, Kruskal's algorithm, and Prim's algorithm.

The idea

Given a connected graph with a weight on every edge, a spanning tree is a set of edges that connects all $n$ vertices and contains no cycle; such a set always has exactly $n - 1$ edges. The minimum spanning tree is a spanning tree of least total weight.

Although a graph can have exponentially many spanning trees, one theorem reduces the search to a sequence of local choices. Call a partition of the vertices into two nonempty sides a cut, and say an edge crosses the cut when its endpoints lie on opposite sides.

Theorem (Cut property).

Suppose the edges chosen so far all belong to some minimum spanning tree and none of them crosses a given cut. Then adding a lightest edge crossing that cut keeps the chosen set inside some minimum spanning tree.

The property holds by an exchange: any spanning tree containing the chosen edges must cross the cut somewhere, and replacing a heavier crossing edge with the lightest one leaves it spanning, acyclic, and no heavier.

Both standard algorithms apply the cut property repeatedly, differing only in which cut they invoke.

Algorithm.

Algorithm: Kruskal Input: a connected weighted graph on n vertices Output: a minimum spanning tree 1. sort the edges into increasing order of weight; no edge chosen yet 2. consider the cheapest edge not yet considered 3. if its endpoints are already connected by chosen edges, skip it // adding it would close a cycle 4. otherwise add it to the chosen edges // cut property: the chosen edges stay inside some minimum spanning tree 5. if fewer than n - 1 edges are chosen, go to step 2 6. return the chosen edges // a minimum spanning tree

Prim's algorithm instead grows a single tree from a starting vertex, each round adding the cheapest edge leaving it. With sorting and the right auxiliary structures, each algorithm computes a minimum spanning tree in $O(E \log V)$ time.

Ways to work on it

Not sure where to start? Take the ten-question placement test.