# Chapter 31. Minimum Spanning Trees # Chapter 31. Minimum Spanning Trees A minimum spanning tree is a spanning tree of least total edge weight. The setting is a connected undirected graph whose edges have weights. The graph may describe a road system, a communication network, a circuit, a clustering problem, or any structure where connecting vertices has a cost. A spanning tree connects all vertices without cycles. A minimum spanning tree chooses such a tree with minimum total cost. Minimum spanning trees are among the basic examples of greedy methods in graph algorithms. Kruskal's algorithm and Prim's algorithm both build a minimum spanning tree by repeatedly choosing locally cheapest safe edges. Their correctness depends on the cut property and the cycle property. ## 31.1 Weighted Graphs Let $$ G = (V,E) $$ be a connected undirected graph. A weight function is a function $$ w : E \to \mathbb{R}. $$ For an edge $$ e \in E, $$ the value $$ w(e) $$ is called the weight, cost, or length of \(e\). If \(T\) is a spanning tree of \(G\), then the weight of \(T\) is $$ w(T)=\sum_{e\in E(T)} w(e). $$ The goal is to find a spanning tree whose total weight is as small as possible. ## 31.2 Definition Let \(G=(V,E)\) be a connected weighted graph. A minimum spanning tree of \(G\) is a spanning tree \(T\) such that $$ w(T) \leq w(T') $$ for every spanning tree \(T'\) of \(G\). The abbreviation MST is commonly used for minimum spanning tree. If \(G\) has \(n\) vertices, every spanning tree has exactly $$ n-1 $$ edges. Thus an MST minimizes the sum of weights among all connected, acyclic, spanning subgraphs. ## 31.3 Example Consider the weighted graph with vertices $$ V=\{A,B,C,D\} $$ and weighted edges: | Edge | Weight | |---|---:| | \(AB\) | \(1\) | | \(AC\) | \(4\) | | \(AD\) | \(3\) | | \(BC\) | \(2\) | | \(BD\) | \(5\) | | \(CD\) | \(6\) | One spanning tree is $$ \{AB,AC,AD\}, $$ with total weight $$ 1+4+3=8. $$ Another spanning tree is $$ \{AB,BC,AD\}, $$ with total weight $$ 1+2+3=6. $$ The second tree has smaller total weight. In fact, it is a minimum spanning tree. ## 31.4 Existence Every finite connected weighted graph has at least one minimum spanning tree. This follows from two facts. First, every finite connected graph has at least one spanning tree. Second, a finite graph has only finitely many spanning trees. Therefore the set of possible spanning tree weights is finite and has a minimum element. If the graph is disconnected, no spanning tree exists. In that case one may instead seek a minimum spanning forest, consisting of one minimum spanning tree in each connected component. ## 31.5 Uniqueness A graph may have more than one minimum spanning tree. For example, if all edge weights are equal, then every spanning tree is a minimum spanning tree. However, distinct edge weights guarantee uniqueness. ### Theorem 31.1 If all edge weights in a connected graph are distinct, then the graph has a unique minimum spanning tree. ### Proof Suppose, for contradiction, that there are two different minimum spanning trees \(T_1\) and \(T_2\). Choose the edge $$ e \in T_1 \setminus T_2 $$ of smallest weight among all edges that belong to exactly one of the two trees. Add \(e\) to \(T_2\). Since \(T_2\) is a tree, this creates exactly one cycle. That cycle contains \(e\). Since \(T_1\) has no cycle, the cycle must contain some edge $$ f \in T_2 \setminus T_1. $$ By the choice of \(e\) and the distinctness of edge weights, $$ w(e) < w(f). $$ Remove \(f\) from \(T_2+e\). The result is another spanning tree, but its total weight is smaller than \(w(T_2)\). This contradicts the assumption that \(T_2\) was minimum. Therefore the minimum spanning tree is unique. ## 31.6 The Cut Property A cut partitions the vertex set into two nonempty parts: $$ S \quad\text{and}\quad V\setminus S. $$ An edge crosses the cut if one endpoint lies in \(S\) and the other endpoint lies in \(V\setminus S\). The cut property says that a lightest edge crossing a cut is safe to use in a minimum spanning tree. In the strict form, if the lightest edge across the cut is unique, then it belongs to every MST. ### Theorem 31.2 Let \(G\) be a connected weighted graph. Let \(e\) be a unique minimum-weight edge crossing some cut. Then every minimum spanning tree of \(G\) contains \(e\). ### Proof Let the cut be $$ (S,V\setminus S). $$ Suppose an MST \(T\) does not contain \(e\). Add \(e\) to \(T\). This creates exactly one cycle. The edge \(e\) crosses the cut, so the cycle must cross the cut again at some other edge \(f\). Since \(e\) is the unique minimum-weight edge crossing the cut, $$ w(e) < w(f). $$ Remove \(f\). The graph remains connected and spanning, and it has the same number of edges as a tree. Hence it is a spanning tree. Its weight is smaller than \(w(T)\), contradicting the minimality of \(T\). Therefore every MST contains \(e\). ## 31.7 The Cycle Property The cycle property gives the dual rule. If an edge is strictly heavier than every other edge on a cycle, then it cannot belong to any minimum spanning tree. ### Theorem 31.3 Let \(C\) be a cycle in a connected weighted graph. If \(e\) is the unique maximum-weight edge on \(C\), then no minimum spanning tree contains \(e\). ### Proof Suppose an MST \(T\) contains \(e\). Remove \(e\) from \(T\). The tree splits into two connected components. Since \(C\) was a cycle, there is another edge \(f\) on \(C\) connecting these two components. Because \(e\) is the unique maximum-weight edge on \(C\), $$ w(f) < w(e). $$ Add \(f\) to \(T-e\). The result is a spanning tree of smaller total weight. This contradicts the assumption that \(T\) was minimum. Therefore \(e\) belongs to no MST. ## 31.8 Kruskal's Algorithm Kruskal's algorithm builds an MST by considering edges in increasing order of weight. It starts with no edges. At each step, it adds the next lightest edge that does not create a cycle. ### Algorithm Input: a connected weighted graph \(G=(V,E)\). 1. Sort the edges by nondecreasing weight. 2. Start with the empty set $$ F=\emptyset. $$ 3. For each edge \(e\), in sorted order: - If adding \(e\) to \(F\) does not create a cycle, add \(e\). - Otherwise, discard \(e\). 4. Stop when \(F\) has $$ |V|-1 $$ edges. The graph $$ (V,F) $$ is a minimum spanning tree. Kruskal's algorithm is usually implemented with a disjoint-set data structure. The disjoint-set structure tracks which connected component each vertex currently belongs to. An edge is accepted exactly when its endpoints lie in different components. ## 31.9 Correctness of Kruskal's Algorithm The correctness of Kruskal's algorithm follows from the cut property. At any step, the accepted edges form a forest. Suppose Kruskal's algorithm considers an edge $$ e=\{u,v\} $$ and accepts it. Then \(u\) and \(v\) lie in different components of the current forest. Let \(S\) be the vertex set of the component containing \(u\). The edge \(e\) crosses the cut $$ (S,V\setminus S). $$ Since the algorithm considers edges in increasing order, no lighter edge crossing this cut is available without already having been considered. Any lighter crossing edge would have joined two different components and would have been accepted earlier. Thus \(e\) is a lightest safe edge across a cut. By the cut property, it can be included in some minimum spanning tree. Repeating this argument for each accepted edge shows that all accepted edges can be extended to an MST. When the algorithm has accepted \(n-1\) edges, it has a spanning tree, and that tree is minimum. ## 31.10 Prim's Algorithm Prim's algorithm grows one tree outward from a starting vertex. It starts with a single vertex. At each step, it adds the lightest edge connecting the current tree to a vertex outside the tree. ### Algorithm Input: a connected weighted graph \(G=(V,E)\). 1. Choose a starting vertex \(s\). 2. Set $$ S=\{s\}. $$ 3. Repeatedly choose a minimum-weight edge crossing the cut $$ (S,V\setminus S). $$ 4. Add the chosen edge and its outside endpoint to the tree. 5. Stop when $$ S=V. $$ The selected edges form a minimum spanning tree. Prim's algorithm is usually implemented with a priority queue, where each outside vertex is keyed by the cheapest edge currently connecting it to the growing tree. ## 31.11 Correctness of Prim's Algorithm Prim's algorithm is a direct application of the cut property. At every step, the current set \(S\) contains the vertices already included in the growing tree. The algorithm chooses a lightest edge crossing the cut $$ (S,V\setminus S). $$ By the cut property, such an edge is safe. Adding it preserves the possibility of completing the selected edges to an MST. After \(n-1\) edge additions, all vertices have been included. The selected edges form a spanning tree. Since every selected edge was safe, the resulting spanning tree is minimum. ## 31.12 Kruskal Compared with Prim Kruskal's algorithm and Prim's algorithm solve the same problem by different growth patterns. | Feature | Kruskal's algorithm | Prim's algorithm | |---|---|---| | Growth pattern | Builds a forest | Builds one tree | | Main choice | Lightest edge avoiding cycles | Lightest edge leaving current tree | | Data structure | Disjoint-set union | Priority queue | | Natural for | Sparse edge lists | Adjacency lists with heaps | | Correctness principle | Cut property | Cut property | Kruskal's algorithm is global: it looks at all edges in increasing order. Prim's algorithm is local: it expands from the current tree boundary. ## 31.13 Time Complexity Let $$ n=|V|, \qquad m=|E|. $$ With sorting and disjoint-set union, Kruskal's algorithm runs in $$ O(m\log m). $$ Since $$ m \leq n^2 $$ in a simple graph, this is also commonly written as $$ O(m\log n). $$ Prim's algorithm depends on the representation and priority queue. With adjacency lists and a binary heap, it runs in $$ O(m\log n). $$ With a Fibonacci heap, the theoretical bound is $$ O(m+n\log n). $$ In practice, simpler priority queues are often preferred unless the graph size and density justify the more complex implementation. ## 31.14 Negative Edge Weights Minimum spanning tree algorithms allow negative edge weights. This differs from some shortest-path algorithms, where negative weights may cause difficulty. For MSTs, only the relative order of edges matters. Kruskal's and Prim's algorithms still work when weights are negative, zero, or positive. A negative edge is simply attractive to include, provided it does not violate the tree structure. ## 31.15 Minimum Bottleneck Spanning Trees The bottleneck of a spanning tree is the maximum edge weight in the tree. A minimum bottleneck spanning tree minimizes this maximum edge weight. Every minimum spanning tree is a minimum bottleneck spanning tree. However, a minimum bottleneck spanning tree need not be a minimum spanning tree. The distinction is important. MST minimizes total cost. Bottleneck optimization minimizes the worst selected edge. ## 31.16 Applications Minimum spanning trees appear in many settings where a network must connect all sites at low cost. | Application | Interpretation | |---|---| | Network design | Connect all locations with minimum total link cost | | Clustering | Remove large MST edges to form clusters | | Image segmentation | Group pixels or regions by similarity | | Approximation algorithms | Build low-cost structures for harder problems | | Circuit design | Connect terminals with short total wiring | | Taxonomy | Build similarity-based hierarchical structure | In each case, the MST gives a sparse global connection pattern. ## 31.17 Limitations A minimum spanning tree minimizes total edge weight, but it does not necessarily minimize distances between pairs of vertices. For example, replacing a dense network by an MST may make some routes much longer. An MST has no redundant paths, so it is fragile: removing any edge disconnects it. Thus MSTs are appropriate when low total connection cost is the main objective. They are less appropriate when redundancy, fault tolerance, low latency, or high capacity are required. ## 31.18 Summary A minimum spanning tree is a spanning tree with minimum total edge weight. The two main structural principles are the cut property and the cycle property. The cut property identifies safe edges. The cycle property identifies edges that cannot be part of an MST. Kruskal's algorithm builds an MST by adding lightest cycle-free edges. Prim's algorithm builds an MST by repeatedly adding the lightest edge leaving the current tree. Both algorithms are greedy. Their correctness comes from the structure of cuts and cycles in weighted graphs.