--- title: 'Minimum Spanning Tree' source: 'https://academia.sh/en/courses/algorithms/minimum-spanning-tree' course: Algorithms language: en updated: '2026-08-17T18:07:38+00:00' license: 'CC BY-SA 4.0' --- # Minimum Spanning Tree The cut property, Prim's and Kruskal's algorithms, the union-find structure, a comparison of the two approaches, and a clustering application. The questions so far concerned the path between two vertices. This lesson changes the question: **what is the cheapest set of edges that connects all vertices to each other?** The question is the basic form of network design: every point must be connected, and the total cable, pipe, or line cost must be minimized. ## The Problem In a weighted, undirected, connected graph, a **spanning tree** is a subgraph that includes every vertex and contains no cycle. Such a subgraph has exactly $V-1$ edges. A **minimum spanning tree (MST)** is the spanning tree whose sum of edge weights is smallest. If the weights are all distinct, the MST is unique; if equal weights exist, more than one MST may exist, and all of them have the same total weight. The graph used throughout this lesson is undirected: ```python edges: list[tuple[int, str, str]] = [ (4, "A", "B"), (2, "A", "C"), (5, "B", "C"), (10, "B", "D"), (3, "C", "E"), (4, "E", "D"), (11, "D", "F"), ] vertices = ["A", "B", "C", "D", "E", "F"] ``` ## The Cut Property Both algorithms are greedy, and their correctness rests on a single observation. A **cut** splits the vertices into two non-empty parts. An edge **crosses** the cut if its endpoints lie in different parts. **Cut property:** The lightest edge crossing any cut is present in some minimum spanning tree. The justification is an **exchange argument**. Let $e$ be the lightest crossing edge, and consider an MST that does not contain it. Adding $e$ to this tree creates a cycle; the cycle must cross the cut at least once more. Let that crossing edge be $f$. Removing $f$ and adding $e$ yields another spanning tree whose weight has not increased, because $e \leq f$. Hence an MST containing $e$ also exists. This property justifies every greedy strategy of the form "take the cheapest edge that is currently safe." The two algorithms differ only in **which cut** they look at. ## Prim's Algorithm The tree starts from a single vertex and grows on every step. The cut examined is the one between the vertices already in the tree and those outside it; the edge chosen is the lightest one crossing this cut. ```python import heapq from collections import defaultdict def build_adjacency(edges: list[tuple[int, str, str]]) -> dict[str, list[tuple[int, str]]]: adjacency: dict[str, list[tuple[int, str]]] = defaultdict(list) for weight, v, w in edges: adjacency[v].append((weight, w)) adjacency[w].append((weight, v)) return adjacency def prim(edges: list[tuple[int, str, str]], start: str) -> tuple[list[tuple[int, str, str]], int]: adjacency = build_adjacency(edges) in_tree = {start} queue = [(weight, start, w) for weight, w in adjacency[start]] heapq.heapify(queue) tree: list[tuple[int, str, str]] = [] while queue: weight, v, w = heapq.heappop(queue) if w in in_tree: # both ends already in the tree: cycle continue in_tree.add(w) tree.append((weight, v, w)) for edge_weight, neighbor in adjacency[w]: if neighbor not in in_tree: heapq.heappush(queue, (edge_weight, w, neighbor)) return tree, sum(weight for weight, _, _ in tree) print(prim(edges, "A")) # ([(2, 'A', 'C'), (3, 'C', 'E'), (4, 'A', 'B'), (4, 'E', 'D'), (11, 'D', 'F')], 24) ``` The structure closely resembles Dijkstra's algorithm; the only difference is that the priority is **distance to the tree**, not **distance from the source**. The cost is also the same: $O(E \log V)$ with a binary heap. ## Kruskal's Algorithm Kruskal does not grow a tree; it sorts the edges by weight and adds them in order. An edge is skipped when its two endpoints are **already in the same component**, since adding it would create a cycle. This check uses a **union-find** structure: a structure that reports, at nearly constant cost, which component each vertex belongs to. ```python class UnionFind: def __init__(self, vertices: list[str]) -> None: self.parent = {v: v for v in vertices} self.rank = {v: 0 for v in vertices} def find(self, v: str) -> str: while self.parent[v] != v: self.parent[v] = self.parent[self.parent[v]] # path compression v = self.parent[v] return v def union(self, a: str, b: str) -> bool: ra, rb = self.find(a), self.find(b) if ra == rb: return False # already the same component if self.rank[ra] < self.rank[rb]: # union by rank ra, rb = rb, ra self.parent[rb] = ra if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1 return True def kruskal(edges: list[tuple[int, str, str]], vertices: list[str]) -> tuple[list[tuple[int, str, str]], int]: components = UnionFind(vertices) tree: list[tuple[int, str, str]] = [] for weight, v, w in sorted(edges): if components.union(v, w): tree.append((weight, v, w)) if len(tree) == len(vertices) - 1: # tree complete break return tree, sum(weight for weight, _, _ in tree) print(kruskal(edges, vertices)) # ([(2, 'A', 'C'), (3, 'C', 'E'), (4, 'A', 'B'), (4, 'E', 'D'), (11, 'D', 'F')], 24) ``` The two algorithms find the same tree on this graph. In general only the **total weight** is guaranteed to match; if equal-weight edges exist, they can produce different trees of equal total weight. The cut here is "the component of one endpoint of the edge being tried" versus the remaining vertices; the edge is the lightest one crossing that cut, because lighter ones have already been tried. When **path compression** and **union by rank** are used together, the amortized cost of union-find operations is nearly constant — its growth is bounded by the inverse Ackermann function and is smaller than four in practice. ## Comparison | Criterion | Prim | Kruskal | |---|---|---| | Approach | Grow the tree | Add edges in order | | Helper structure | Priority queue | Union-find | | Cost | $O(E \log V)$ | $O(E \log E)$ | | Dense graph | Suits it (array variant gives $O(V^2)$) | Sorting dominates | | Disconnected graph | Finds only one component | Produces a spanning **forest** | Sorting dominates Kruskal's cost; if the edges are already sorted, the cost drops to nearly linear. Prim gains the edge as the edge count approaches the square of the vertex count. One distinction is decisive in practice: if the graph is not connected, Kruskal produces one tree per component, and the result is a spanning forest; Prim covers only the component of the starting vertex. ## A Clustering Application Kruskal's intermediate steps are meaningful on their own: when the algorithm has added $V-k$ edges, $k$ components remain, and these components are the $k$ clusters that are **farthest apart from each other**. This is the single-linkage clustering method: distances between points are treated as edge weights, an MST is built, and the heaviest $k-1$ edges are discarded. The result is the split that maximizes the minimum distance between clusters. The same structure is also used in network design and in approximate solutions: in the metric case of the traveling salesman problem, the MST gives a lower bound on the length of the optimal tour and helps produce a tour that does not exceed twice that length. ## Summary - A spanning tree connects all vertices acyclically and contains $V-1$ edges; a minimum spanning tree is the lightest of these. - The cut property states that the lightest edge crossing any cut is present in some MST, and it justifies the greedy choices. - Prim grows a tree and uses a priority queue; its cost is $O(E \log V)$. - Kruskal sorts edges and checks cycles with union-find; its cost is $O(E \log E)$. - Path compression and union by rank make union-find operations amortized nearly constant. - Kruskal's intermediate states produce clustering; an MST also provides a lower bound in approximate solutions. ## Next Step Until now, edges carried a cost. The next lesson gives edges a different meaning: **capacity**. How much can be pushed from a source to a target through a network is now an optimization problem defined on a graph, and its answer arrives with an unexpected equality — the equality between maximum flow and minimum cut.