Minimum Spanning Trees

Let G = (V, E, w) be a connected undirected weighted graph with vertex set V (|V| = n), edge set E (|E| = m), and weight function w: E → ℝ. A spanning tree T is a subgraph of G that (1) includes all n vertices, (2) is connected, and (3) is acyclic. Any spanning tree has exactly n-1 edges — a consequence of the tree identity.

A minimum spanning tree is a spanning tree T* that minimizes the total weight:

w(T*) = min over all spanning trees T of { Σ_{e ∈ T} w(e) }

Uniqueness: If all edge weights are distinct, the MST is unique. If weights can repeat, there may be multiple MSTs but they all have the same total weight (though their edge sets may differ).

Why a tree? A spanning connected subgraph with the minimum possible edges is a tree. If we had a cycle, we could remove the most expensive edge in that cycle without disconnecting the graph, reducing total cost — so any minimum-cost spanning connected subgraph must be acyclic, hence a tree.

This last argument is important: it shows the MST problem is well-defined and that the optimum is always achieved by a tree, not some other subgraph.

# A weighted graph as an edge list
# (u, v, weight)
edges = [
    (0, 1, 4),
    (0, 2, 3),
    (1, 2, 1),
    (1, 3, 2),
    (2, 3, 4),
    (3, 4, 2),
    (2, 4, 5),
]
# n=5 vertices (0..4), MST will have exactly 4 edges

The cut property is the theorem that unifies and justifies all MST algorithms. Understanding it is more important than memorizing any pseudocode.

Definition — Cut: A cut of G is a partition of V into two non-empty sets S and V\S. The cut set (or crossing edges) is the set of edges with one endpoint in S and one in V\S.

Cut Property Theorem: Let S be any cut of G, and let e = (u, v) be the unique minimum-weight edge crossing that cut. Then e belongs to every MST of G.

Proof (by exchange argument): Suppose for contradiction that some MST T does not contain e. Since T is a spanning tree, there is a unique path P in T from u to v. This path must cross the cut at least once (since u ∈ S and v ∈ V\S), so it contains some crossing edge e' ≠ e. Since e is the unique minimum crossing edge, w(e) < w(e'). Now form T' = T ∪ {e} − {e'}. Adding e to T creates exactly one cycle (the path P plus e), and removing e' from that cycle restores acyclicity. T' is still a spanning tree. But w(T') = w(T) + w(e) − w(e') < w(T), contradicting the minimality of T. ∎

Consequence: We can greedily add any minimum-weight cut edge to our MST without fear of making a mistake. Both Kruskal and Prim exploit this at every step — they differ only in which cut they choose.

The Cycle Property (dual): The maximum-weight edge on any cycle is never in any MST (assuming distinct weights). If weights are non-distinct, it is not required to be in any MST. This property is the basis of the correctness argument for removing edges.

Kruskal's algorithm is the most intuitive: sort all edges by weight and process them cheapest-first. When you consider edge e = (u, v), add it to the MST if and only if u and v are not already connected in the current forest. Stop when you have n-1 edges.

Why this is correct: Each time we add an edge (u, v), consider the cut S = the connected component of u in the current forest. The edge (u, v) is the lightest edge leaving S (we process edges in order, and we only add it when u and v are in different components, meaning this is the first edge we have seen that crosses this cut). By the cut property, it is safe to add.

Complexity:

• Sorting: O(m log m) = O(m log n) since m ≤ n²
• For each of the m edges: one union-find operation
• With efficient union-find (see below): nearly O(m α(n)) for the union-find part
• Total: O(m log m), dominated by sorting

Kruskal's is excellent for sparse graphs (m ≈ n) since the log factor is small. It is also easy to implement and parallelize (the sort is the bottleneck).

def kruskal(n, edges):
    """n = number of vertices (0..n-1)
    edges = list of (weight, u, v)
    Returns list of MST edges."""
    edges.sort()          # O(m log m)
    uf = UnionFind(n)
    mst = []
    for w, u, v in edges:
        if uf.find(u) != uf.find(v):   # different components
            uf.union(u, v)
            mst.append((w, u, v))
            if len(mst) == n - 1:
                break   # done
    return mst

Kruskal's algorithm needs to answer the query "are u and v in the same connected component?" and to merge two components. A naive approach (DFS/BFS) costs O(n) per query. Union-find answers both operations in amortized O(α(n)) time — where α is the inverse Ackermann function, slower-growing than log log log n, essentially a constant for all practical n.

Structure: Maintain a forest of trees. Each element x has a parent[x]. The root of each tree is the canonical representative ("find representative") of its component.

Find(x): Walk up the parent pointers to the root.

Union(x, y): Find the roots of x and y. If different, make one the parent of the other.

Trick 1 — Union by Rank: When merging, attach the shorter tree under the root of the taller tree (rank = upper bound on height). This keeps trees shallow (height ≤ log n) without any other trick.

Trick 2 — Path Compression: During Find(x), after reaching the root, go back and set parent[node] = root for every node on the path. Future Find calls on the same nodes are O(1). This is the key to the near-O(1) amortized cost.

Together: Union by rank + path compression yields amortized O(α(n)) per operation. α(n) ≤ 4 for n < 10^80 — for all practical purposes, constant.

Implementation: The code below is self-contained and covers both tricks.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # each node is its own root
        self.rank = [0] * n           # upper bound on subtree height

    def find(self, x):
        # Path compression: flatten the tree as we walk up
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # recursive compression
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False   # already same component
        # Union by rank: attach smaller tree under larger
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True

Prim's algorithm takes a different approach: start from any single vertex and grow the MST outward, one vertex at a time, always extending by the cheapest edge that crosses the boundary between the current tree and the rest of the graph.

Invariant: At each step, we maintain a set S (the "tree so far") and a key for each vertex v ∉ S: key[v] = minimum weight edge from any vertex in S to v. We always pick the vertex u ∉ S with the smallest key, add it to S, and update the keys of u's neighbors.

Why this is correct: At every step, the cut is (S, V\S). The edge (parent[u], u) with weight key[u] is the minimum-weight crossing edge for this cut. By the cut property, it is safe to add.

Complexity depends on data structure:

• With a binary min-heap (Python heapq): O((n + m) log n) = O(m log n)
• With a Fibonacci heap: O(m + n log n) — optimal for dense graphs

Prim's is typically preferred for dense graphs (m ≈ n²) with a Fibonacci heap, where it beats Kruskal's O(m log m). For sparse graphs both are O(m log n).

Implementation note: Python's heapq does not support decrease-key, so the standard trick is to push duplicate (key, v) entries and skip stale ones with a visited set.

import heapq

def prim(n, adj):
    """adj[u] = list of (weight, v)
    Returns MST as list of (weight, u, v) edges."""
    visited = [False] * n
    # (weight, to_vertex, from_vertex)
    heap = [(0, 0, -1)]   # start from vertex 0
    mst = []
    total = 0

    while heap and len(mst) < n - 1:
        w, u, parent = heapq.heappop(heap)
        if visited[u]:
            continue        # stale entry, skip
        visited[u] = True
        if parent != -1:
            mst.append((w, parent, u))
            total += w
        for weight, v in adj[u]:
            if not visited[v]:
                heapq.heappush(heap, (weight, v, u))

    return mst, total

Both Kruskal and Prim are instances of a single generic MST algorithm. Understanding the generic algorithm makes both proofs trivial.

Generic MST Algorithm:

1. Start with A = ∅ (the set of edges in our MST so far).
2. While A does not form a spanning tree: a. Find an edge e that is safe to add to A (i.e., A ∪ {e} is a subset of some MST). b. Add e to A.
3. Return A.

Key Definition — Safe Edge: An edge (u, v) is safe for A if there exists an MST T such that A ⊆ T and (u,v) ∈ T.

Generic Correctness Theorem (CLRS): Let A be a subset of some MST. Let (S, V\S) be any cut that respects A (no edge in A crosses the cut). Let e be a minimum-weight crossing edge. Then e is safe for A.

Proof: Let T be any MST with A ⊆ T. If e ∈ T, done. Otherwise, T ∪ {e} contains a cycle C. Since e crosses the cut, C contains another crossing edge e'. Note e' ∉ A (the cut respects A). Form T' = T ∪ {e} − {e'}. T' is a spanning tree. Since w(e) ≤ w(e'), w(T') ≤ w(T), so T' is also an MST. And A ∪ {e} ⊆ T'. ∎

Kruskal as instance: At each step, the cut S = connected component of u in the current forest A. The minimum-weight crossing edge is the current edge (u,v) if u and v are in different components.

Prim as instance: At each step, S = the current tree. The minimum-weight crossing edge is always the one selected by the priority queue.

Both algorithms find the MST, but they have different strengths:

Dense vs. sparse crossover: For dense graphs m = Θ(n²):

• Kruskal: O(n² log n)
• Prim with Fibonacci heap: O(n²) — better

For sparse graphs m = Θ(n):

• Both are O(n log n)

Practical note: In competitive programming and production code, Kruskal with union-find is almost always preferred because union-find is simpler to implement correctly than a Fibonacci heap. Prim with a binary heap is used when an adjacency-list representation is more natural.

Borůvka's algorithm (the oldest, from 1926) is a third option: in each round, every component picks its cheapest outgoing edge and all those edges are added simultaneously. It halves the number of components each round, giving O(m log n) and excellent parallelism — it is used in distributed graph systems.

MSTs provide an elegant, parameter-free approach to single-linkage hierarchical clustering.

The connection: Build the MST of a complete graph where vertices are data points and edge weights are distances (Euclidean, cosine, etc.). Now sort the MST edges by weight and remove the k-1 heaviest edges. The remaining forest has exactly k connected components — these are your k clusters.

Why this is equivalent to single-linkage clustering: Single-linkage defines the distance between two clusters as the minimum distance between any point in one and any point in the other. The MST represents the full single-linkage dendrogram: removing the heaviest edge corresponds to cutting the dendrogram at the highest merge.

Algorithm:

1. Compute pairwise distances: O(n²)
2. Build MST on complete graph: O(n² log n) with Kruskal or O(n²) with Prim
3. Remove k-1 heaviest MST edges
4. Output connected components

Advantage over k-means: Finds non-convex clusters. Works without specifying the number of clusters upfront (you can inspect the edge weights to choose k).

Limitation: Single-linkage (and MST-based clustering) suffers from chaining: a single "bridge" point between two natural clusters will merge them. It is sensitive to noise and outliers.

Example: In the famous MNIST digit visualization, MST-based clustering shows which digit classes are topologically close — 4 and 9 are nearby, 0 and 6 are nearby — forming an interpretable neighborhood structure.

import numpy as np

def mst_cluster(points, k):
    """Cluster `points` into k groups via MST."""
    n = len(points)
    # Build complete edge list with Euclidean distances
    edges = []
    for i in range(n):
        for j in range(i + 1, n):
            d = np.linalg.norm(points[i] - points[j])
            edges.append((d, i, j))

    # Kruskal's MST
    edges.sort()
    uf = UnionFind(n)
    mst_edges = []
    for d, u, v in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst_edges.append((d, u, v))

    # Remove k-1 heaviest edges → k clusters
    mst_edges.sort(reverse=True)
    cut_uf = UnionFind(n)
    kept = mst_edges[k - 1:]   # keep the n-k cheapest
    for d, u, v in kept:
        cut_uf.union(u, v)

    return [cut_uf.find(i) for i in range(n)]

MSTs are the theoretical foundation for a wide class of network design problems:

Telecommunications: A telephone company wants to lay cables between cities. The MST gives the cheapest network ensuring connectivity. In practice, variants are used: the Steiner tree problem (a small subset of nodes must be connected, using other nodes only as relay points) is NP-hard, but MST-based heuristics with 2x approximation ratio are common.

Power grids: Electrical utilities design transmission networks using MST-based algorithms to minimize total wire length while ensuring connectivity.

VLSI layout: Connecting chip components with minimum wire uses MST (in rectilinear metric). Reducing wire length reduces capacitance and propagation delay.

Approximation algorithms: The MST is the backbone of the 2-approximation for Metric TSP (Traveling Salesman Problem). Algorithm: (1) build MST, (2) perform a DFS traversal to get an Eulerian path, (3) shortcut repeated vertices. The resulting tour has cost ≤ 2 × OPT.

Image segmentation: Felzenszwalb-Huttenlocher segmentation builds an MST on a pixel graph (edges = color difference) and cuts it based on local edge weight statistics, yielding perceptually natural segments efficiently.

Distributed spanning trees: In network routing (e.g., Spanning Tree Protocol in Ethernet switches), distributed versions of Prim/Borůvka run across network nodes to prevent broadcast loops — every Ethernet switch runs a protocol based on these ideas.

Borůvka's algorithm (Otakar Borůvka, 1926 — the oldest MST algorithm) is different from both Kruskal and Prim in a way that makes it naturally parallel.

Algorithm:

1. Start with n components (each vertex is its own component).
2. Repeat until there is only one component: a. For each component C, find the minimum-weight edge e_C leaving C. b. Add all such edges to the MST (handling duplicates — if two components pick the same edge, add it once).
3. Return the MST.

Analysis: Each round at least halves the number of components (each pair of components that pick each other's cheapest edge merge). So there are at most O(log n) rounds. Each round scans all edges once: O(m). Total: O(m log n).

Why it is parallel: In each round, every component independently finds its cheapest outgoing edge — these lookups are independent and can run on separate processors. Adding edges is a parallel merge operation. This is the algorithm behind Parallel MST on shared-memory machines and distributed graph systems.

MapReduce / Spark: Borůvka maps naturally onto the MapReduce paradigm: in each map phase, each edge reports to its component which is cheapest; in the reduce phase, components collect their minimum and merge. Modern distributed graph frameworks (GraphX, Pregel) implement Borůvka variants for massive graphs.

def boruvka(n, edges):
    """n vertices, edges = list of (w, u, v). Returns MST edge list."""
    uf = UnionFind(n)
    mst = []
    num_components = n

    while num_components > 1:
        # cheapest[comp] = (weight, u, v) or None
        cheapest = [None] * n

        for w, u, v in edges:
            ru, rv = uf.find(u), uf.find(v)
            if ru == rv:
                continue  # same component, skip
            if cheapest[ru] is None or w < cheapest[ru][0]:
                cheapest[ru] = (w, u, v)
            if cheapest[rv] is None or w < cheapest[rv][0]:
                cheapest[rv] = (w, u, v)

        for comp in range(n):
            if cheapest[comp] is None:
                continue
            w, u, v = cheapest[comp]
            if uf.find(u) != uf.find(v):
                uf.union(u, v)
                mst.append((w, u, v))
                num_components -= 1

    return mst