Minimum Spanning Trees

For a connected, weighted, undirected graph, a minimum spanning tree (MST) connects all vertices without cycles and minimizes total edge weight. It minimizes total tree weight, not the path distance between every pair.

Cut property

For a cut that divides vertices into two sets, a minimum-weight edge crossing the cut is safe for some MST. This property supports both major algorithms.

Kruskal's algorithm

1. Sort all edges by nondecreasing weight.
2. Scan them in order.
3. Add an edge exactly when its endpoints are in different disjoint sets.

Union–find makes the cycle test efficient. Sorting dominates at O(E log E), equivalent to O(E log V) for ordinary simple-graph bounds. A disconnected input produces a minimum spanning forest.

Prim's algorithm

Start from any vertex and repeatedly add the lightest edge crossing from the current tree to an outside vertex. With adjacency lists and a binary heap, time is O(E log V).

Uniqueness

Distinct edge weights imply a unique MST, but equal weights do not necessarily imply multiple MSTs. Tie-breaking can select different valid trees with the same minimum total weight.

Exercises

1. Trace Kruskal using the disjoint-set structure.
2. Give a graph whose shortest-path tree is not an MST.
3. Prove that adding one edge to a tree creates exactly one cycle.