Cây khung nhỏ nhấtMinimum Spanning Trees

Part of the Data Structures & Algorithms Roadmap knowledge base.

Overview

You have a set of locations and a set of possible connections between them, each with a cost. You want every location reachable from every other, and you want to pay as little as possible. That is the minimum spanning tree (MST) problem, and it is one of the few genuinely important problems where the obvious greedy strategy is not merely a decent heuristic — it is provably optimal.

The applications are exactly what the framing suggests. Laying fibre to connect a set of buildings. Wiring a circuit board with the least total trace length. Designing a backbone network topology. But the MST also shows up where the “network” is metaphorical: single-linkage clustering is literally “build the MST and delete the k−1 heaviest edges”; image segmentation algorithms build an MST over a pixel-similarity graph; the standard 2-approximation for the metric travelling salesman problem starts by building an MST; maze generation is an MST over a grid with random edge weights.

What makes MST worth studying carefully is not the algorithms — Kruskal’s and Prim’s are each about fifteen lines — but why they are correct. Both are greedy, and greedy algorithms are usually wrong (see ./20-brute-force-greedy-and-randomised-algorithms.md). Here they are right, and the reason is two structural facts about spanning trees: the cut property and the cycle property. Understand those and both algorithms become obvious; skip them and you are memorizing code.

MSTs are defined on undirected, connected, weighted graphs. Direction changes the problem into finding a minimum spanning arborescence, a different and harder problem solved by the Chu-Liu/Edmonds algorithm. This note assumes the representations and traversals from ./13-graph-data-structures.md.

Fundamentals

Spanning trees

A spanning tree of a connected undirected graph G = (V, E) is a subgraph that:

1. includes every vertex (“spanning”),
2. is connected, and
3. contains no cycle (“tree”).

Any two of those three conditions, plus an edge count of exactly V − 1, imply the third. This gives four equivalent characterizations, all worth having to hand:

• connected + acyclic
• connected + exactly V − 1 edges
• acyclic + exactly V − 1 edges
• exactly one simple path between every pair of vertices

Graph G: a square with one diagonal.

   0 --- 1        edge weights:  0-1 : 1
   | \   |                       0-2 : 4
   |  \  |                       0-3 : 2
   2 --- 3                       1-3 : 3
                                 2-3 : 5

Spanning tree T1 = {0-1, 0-3, 0-2}      Spanning tree T2 = {0-1, 1-3, 2-3}
weight 1 + 2 + 4 = 7 (this is the MST)  weight 1 + 3 + 5 = 9

   0 --- 1                                 0 --- 1
   | \                                           |
   |  \                                          |
   2    3                                 2 --- 3

Adding any non-tree edge to a spanning tree creates exactly one cycle (because there was already exactly one path between its endpoints). Removing any tree edge splits the tree into exactly two components. These two facts are the machinery behind every proof below.

A connected graph usually has an enormous number of spanning trees — the complete graph K_n has n^(n−2) of them by Cayley’s formula, which is 10^8 for just ten vertices. Enumerating them to find the cheapest is out of the question, which is why the greedy properties matter.

A minimum spanning tree is a spanning tree whose total edge weight is minimum among all spanning trees. If the graph is disconnected there is no spanning tree at all; what you get instead is a minimum spanning forest — one MST per connected component.

The cut property

A cut (S, V∖S) is any partition of the vertices into two non-empty sets. An edge crosses the cut if it has one endpoint in each side.

Cut property. For any cut, if e is the unique minimum-weight edge crossing that cut, then e belongs to every MST of the graph.

(With ties, the weaker statement holds: some minimum-weight crossing edge belongs to some MST.)

Proof (exchange argument). Suppose T is an MST that does not contain e = (u, v), with u ∈ S and v ∈ V∖S. T is spanning, so it contains a path from u to v. That path starts in S and ends outside it, so at some point it uses an edge f that also crosses the cut. Since e is the unique minimum crossing edge, w(e) < w(f). Now form T' = T − f + e. Removing f splits T into two pieces, and e reconnects them (it joins the same two sides of the cut), so T' is again a spanning tree — with weight w(T) − w(f) + w(e) < w(T). That contradicts T being minimum. ∎

Cut (S, V\S):        S  |  V\S
                        |
              u --------|-------- v      e, weight 2  <- unique minimum crossing edge
                        |
              a --------|-------- b      f, weight 7
                        |
              c --------|-------- d      g, weight 5

Every MST contains e. No proof by inspection needed - the exchange argument
above works for any cut whatsoever.

This single property justifies both algorithms. Prim’s grows a set S and repeatedly adds the cheapest edge leaving S — a cut, by construction. Kruskal’s adds the cheapest edge joining two different components — which is the cheapest edge crossing the cut that separates one of those components from everything else. Both are just the cut property applied over and over.

The cycle property

Cycle property. For any cycle C in the graph, if f is the unique maximum-weight edge on C, then f belongs to no MST.

Proof. Suppose an MST T contains f = (u, v). Remove f: T splits into two components, with u in one and v in the other. The rest of the cycle C forms a u-to-v path, which must cross back between the two components at some edge g ≠ f. Then T − f + g is a spanning tree with weight w(T) − w(f) + w(g) < w(T) since w(g) < w(f). Contradiction. ∎

The cycle property is the exclusion rule that mirrors the cut property’s inclusion rule. Kruskal’s uses it implicitly: when it skips an edge because both endpoints are already connected, that edge is the heaviest on the cycle it would close (all lighter edges of that cycle were considered earlier). This is also the basis of the “reverse-delete” algorithm — sort edges descending and delete each one whose removal keeps the graph connected — which is correct but slow and rarely used.

Together the two properties are what algorithm textbooks call the blue rule (colour a minimum crossing edge blue: it is in the MST) and the red rule (colour a maximum cycle edge red: it is out). Every MST algorithm is a scheduling policy over these two rules.

MST uniqueness

If all edge weights are distinct, the MST is unique.

Proof. Suppose T₁ ≠ T₂ are both MSTs. Let e be the minimum-weight edge in their symmetric difference — say e ∈ T₁ ∖ T₂ (the argument is symmetric). Adding e to T₂ creates exactly one cycle C. C cannot lie entirely inside T₁ (a tree has no cycles), so C contains some edge f ∉ T₁, and f ≠ e. Then f ∈ T₂ ∖ T₁, so f is also in the symmetric difference, and by the minimality of e with distinct weights, w(e) < w(f). Then T₂ − f + e is a spanning tree of strictly smaller weight than T₂. Contradiction. ∎

The converse does not hold: an MST can be unique even with repeated weights. What ties actually cause is ambiguity of the algorithm’s output, not necessarily multiple MSTs — two runs of Kruskal’s with different tie-breaking may emit different edge sets, though both will have the same total weight.

Practical consequence: if you need a deterministic, reproducible MST, break ties deterministically. Sorting edges by (weight, u, v) rather than by weight alone makes Kruskal’s output stable across runs and across Python versions.

Other properties worth knowing

• Every MST is a minimum bottleneck spanning tree. The MST minimizes not only the total weight but also the maximum edge weight over all spanning trees. That is why the MST answers “connect everything while keeping the worst single link as good as possible.” The converse is false — a minimum bottleneck spanning tree need not be an MST.
• The MST is invariant under any strictly increasing transform of the weights. Squaring all weights, or taking logs, or adding a constant, leaves the MST unchanged — because the algorithms only ever compare weights. (Contrast this sharply with shortest paths, where adding a constant to every weight changes the answer; see ./14-shortest-path-algorithms.md.)
• A maximum spanning tree is found by negating all weights and running any MST algorithm, or equivalently by sorting descending in Kruskal’s.
• The MST is not a shortest-path tree. These are different objects and confusing them is a classic error. In a triangle with w(A,B) = 1, w(B,C) = 1, w(A,C) = 1.9, the MST is {AB, BC} (total 2), but the shortest-path tree from A is {AB, AC} because d(A,C) = 1.9 < 2. The MST minimizes total edge weight; a shortest-path tree minimizes each root-to-vertex distance.
• The MST edge set is a matroid basis (of the graphic matroid), which is the abstract reason greedy works here and the general theory behind “when is greedy correct.”

Key Concepts

Kruskal’s algorithm — sort the edges, O(E log E)

Kruskal’s is the cut property applied globally: consider edges from cheapest to most expensive, and take each one unless it would create a cycle. “Would create a cycle” means “both endpoints are already in the same component”, which is exactly the query a disjoint-set union (union-find) structure answers in near-constant time — see ./16-disjoint-set-union-find.md for the full treatment of the structure used here.

class DSU:
    """Disjoint-set union with union by size and path halving.
    find/union are O(alpha(n)) amortized - effectively constant.
    Full treatment in ./16-disjoint-set-union-find.md."""

    def __init__(self, n):
        self.parent = list(range(n))     # every element starts in its own set
        self.size = [1] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path halving
            x = self.parent[x]
        return x

    def union(self, a, b):
        """Merge the sets of a and b. Returns False if they were already merged."""
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                 # same component: this edge would close a cycle
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra              # union by size: hang the small tree off the big
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        return True


def kruskal(n, edges):
    """Minimum spanning tree of an undirected graph.

    `edges` is a list of (w, u, v) triples - the edge-list representation.
    Returns (total_weight, mst_edges). Raises if the graph is disconnected.
    Time O(E log E) dominated by the sort; space O(V + E).
    """
    edges = sorted(edges)                # (w, u, v) sorts by weight, then u, then v
    dsu = DSU(n)
    total = 0
    mst = []

    for w, u, v in edges:
        if dsu.union(u, v):              # different components -> safe to take
            total += w
            mst.append((w, u, v))
            if len(mst) == n - 1:
                break                    # a spanning tree has exactly n-1 edges

    if len(mst) != n - 1:
        raise ValueError("graph is not connected - no spanning tree exists")
    return total, mst

Why it is correct. When Kruskal’s accepts edge (u, v), consider the cut separating u’s current component from everything else. Every edge crossing that cut with weight less than w was already examined and rejected — but rejection only happens for edges inside a component, so no such crossing edge exists. Therefore (u, v) is a minimum-weight edge across that cut, and the cut property says it belongs to an MST. Every edge it rejects is the maximum-weight edge on the cycle it would close, excluded by the cycle property.

Complexity: O(E log E) time. The sort dominates at O(E log E); the E union-find operations cost O(E · α(V)) where α is the inverse Ackermann function — under 5 for any input that fits in the universe. Since E ≤ V², log E ≤ 2 log V, so O(E log E) = O(E log V); both forms appear in the literature and mean the same thing. Space is O(V) for the DSU plus O(E) for the sorted edge list.

When the sort is free, Kruskal’s becomes O(E α(V)) — effectively linear. That happens when weights are small integers (counting sort or bucket sort, see ./08-sorting-algorithms.md) or when edges arrive already sorted. This is Kruskal’s biggest practical advantage.

Two nice properties fall out of the structure:

• Disconnected input is handled naturally. Drop the raise and Kruskal’s returns the minimum spanning forest — the MST of each component — without any change to the loop.
• Incremental / online use. Because it processes edges independently, you can feed edges from a stream, or stop early once n − 1 edges are taken.

Prim’s algorithm — grow one tree, O(E log V)

Prim’s is the cut property applied locally: start from an arbitrary vertex, and repeatedly add the cheapest edge that connects the tree built so far to a vertex outside it. The cut is (tree, everything else) and it changes at every step.

Graph G from above. Start at 0; the tree grows one vertex at a time and
the cut (tree | rest) moves with it.

step 0:  tree = {0}          cheapest edge leaving: 0-1 (w=1)  -> take it
step 1:  tree = {0,1}        candidates 0-2 (4), 0-3 (2), 1-3 (3) -> take 0-3 (2)
step 2:  tree = {0,1,3}      candidates 0-2 (4), 2-3 (5)          -> take 0-2 (4)
step 3:  tree = {0,1,2,3}    done - n-1 = 3 edges, total weight 7

The “cheapest edge leaving the tree” query is what a priority queue is for — see ./12-heaps-and-priority-queues.md.

import heapq


def prim(adj, start=0):
    """Minimum spanning tree by growing a single tree from `start`.

    adj[u] is a list of (v, w) pairs. Returns (total_weight, mst_edges).
    Time O(E log V), space O(V + E).

    This is the "lazy" variant: instead of decrease-key (which heapq lacks) it
    pushes duplicates and discards stale entries on pop.
    """
    n = len(adj)
    in_tree = [False] * n
    pq = [(0, start, -1)]                # (edge weight, vertex, vertex we came from)
    total = 0
    mst = []

    while pq:
        w, u, p = heapq.heappop(pq)
        if in_tree[u]:
            continue                     # stale entry: u joined the tree already
        in_tree[u] = True
        if p != -1:                      # -1 marks the artificial start entry
            total += w
            mst.append((w, p, u))
        for v, wv in adj[u]:
            if not in_tree[v]:
                heapq.heappush(pq, (wv, v, u))

    if len(mst) != n - 1:
        raise ValueError("graph is not connected - no spanning tree exists")
    return total, mst

Complexity: O(E log E) = O(E log V). Every edge is pushed at most once from each endpoint, so the heap holds O(E) entries; each push and pop costs O(log E). Space is O(E) for the heap — the price of the lazy approach.

The eager variant keeps one heap entry per vertex (its cheapest known connection to the tree) and uses decrease-key, giving O(V) heap space and O(E log V) time. In Python without a decrease-key primitive, the lazy version is what you write; in C++ with std::priority_queue the same applies. With a Fibonacci heap, Prim’s is O(E + V log V), matching the theoretical optimum for a comparison-based approach.

On a dense graph, drop the heap entirely. Keep a key[] array of “cheapest edge from the tree to this vertex” and pick the minimum by linear scan:

def prim_dense(matrix):
    """Prim's for a dense graph given as an adjacency matrix (INF = no edge).

    Time O(V^2), space O(V) beyond the matrix. When E is close to V^2 this beats
    the heap version: O(V^2) < O(V^2 log V).
    """
    n = len(matrix)
    INF = float("inf")
    key = [INF] * n                      # cheapest known edge weight into each vertex
    parent = [-1] * n
    in_tree = [False] * n
    key[0] = 0
    total = 0

    for _ in range(n):
        u = -1
        for v in range(n):               # O(V) scan for the cheapest fringe vertex
            if not in_tree[v] and (u == -1 or key[v] < key[u]):
                u = v
        if key[u] == INF:
            raise ValueError("graph is not connected - no spanning tree exists")
        in_tree[u] = True
        total += key[u]
        for v in range(n):               # O(V) relaxation of the cut
            if not in_tree[v] and matrix[u][v] < key[v]:
                key[v] = matrix[u][v]
                parent[v] = u

    return total, parent

The resemblance to Dijkstra is not a coincidence, but the two are not the same algorithm. Both grow a set greedily from a priority queue. The difference is one line: Dijkstra’s key is dist[u] + w (cost from the source), Prim’s key is just w (cost of the single connecting edge). That is why Dijkstra produces a shortest-path tree and Prim’s produces an MST, and why Dijkstra breaks on negative weights while Prim’s does not care — Prim’s never accumulates, so there is nothing for a negative weight to corrupt.

Kruskal’s or Prim’s?

The short version:

• Sparse graph (E ≈ V) — either works; Kruskal’s is usually simpler, and if weights are small integers it becomes effectively linear.
• Dense graph (E ≈ V²) — use prim_dense. O(V²) beats O(V² log V) and it allocates nothing. This is the same reasoning as array-based versus heap-based Dijkstra.
• Edges arriving as a stream, or already sorted — Kruskal’s, which never needs random access to neighbours.
• You already hold an adjacency list and want to avoid building an edge list — Prim’s.
• Disconnected graph and you want the forest — Kruskal’s, which does it for free; Prim’s needs an outer loop over unvisited start vertices.

Borůvka’s algorithm (1926 — the first MST algorithm ever published, predating both) is worth knowing about: in each round, every component simultaneously picks its own cheapest outgoing edge, and all those edges are added at once. Each round at least halves the number of components, so there are O(log V) rounds, each costing O(E) — total O(E log V). Because the per-round work is embarrassingly parallel, it is the basis of parallel and distributed MST implementations, and of the theoretically fastest known algorithms (the Karger-Klein-Tarjan randomized O(E) expected-time algorithm, and Chazelle’s O(E α(V)) deterministic one). Borůvka’s requires distinct edge weights to be correct as stated — with ties, two components can each pick “the other’s” edge and form a cycle — which is fixed by breaking ties on edge index.

Applications

Network design. The original motivating problem. Connect n offices with leased lines, n houses to a water main, n components on a PCB — minimize total cable while keeping everything connected. Note the assumption baked in: the MST optimizes total cost with no regard for path lengths within the network. If latency between any two nodes matters, an MST is the wrong shape (it can be a long path), and you want something else entirely — a shortest-path tree, or a topology with redundancy. The MST is also the minimum redundancy topology: remove any edge and the network partitions. Real backbones deliberately add edges beyond the MST for fault tolerance.

Single-linkage clustering. To split n points into k clusters where “distance between clusters” means the distance between their two closest members: build the MST over the complete distance graph, then delete the k − 1 heaviest edges. The k remaining components are exactly the single-linkage clusters, and the weight of the lightest deleted edge is the spacing — the minimum inter-cluster distance — which this construction provably maximizes.

def single_linkage_clusters(n, edges, k):
    """Split n points into k clusters by cutting the k-1 heaviest MST edges.

    `edges` is a list of (distance, i, j). Returns (labels, spacing) where
    `spacing` is the minimum distance between two different clusters.
    Time O(E log E).
    """
    _, mst = kruskal(n, edges)
    mst.sort()                                    # ascending by weight
    keep = mst[:len(mst) - (k - 1)]               # drop the k-1 heaviest edges
    spacing = mst[len(mst) - (k - 1)][0] if k > 1 else float("inf")

    dsu = DSU(n)
    for w, u, v in keep:
        dsu.union(u, v)
    labels = [dsu.find(x) for x in range(n)]
    return labels, spacing

Note the practical caveat: single-linkage suffers from chaining — a thin bridge of intermediate points merges two otherwise well-separated clusters, because only the single closest pair matters. That is a property of the objective, not a bug in the algorithm, and it is why complete-linkage or Ward clustering are often preferred on real data.

Approximate TSP. For a metric graph (weights satisfy the triangle inequality), building an MST, doubling every edge, and taking an Euler tour with shortcuts yields a tour at most twice the optimal — because the MST is cheaper than the optimal tour (delete any tour edge and you get a spanning path, hence a spanning tree). Christofides’ algorithm refines the same idea to a 1.5-approximation.

Maze generation. Assign random weights to the walls of a grid and compute the MST: the result is a perfect maze — exactly one path between any two cells, by the spanning-tree property. Randomized Kruskal’s and randomized Prim’s are two of the standard maze algorithms and produce visibly different maze textures (Kruskal’s gives many short dead ends; Prim’s gives a more radial structure).

Image segmentation. Felzenszwalb-Huttenlocher segmentation builds a graph over pixels with edges weighted by colour difference and merges regions in MST order, subject to a threshold that adapts to region size. Union-find does the merging, exactly as in Kruskal’s.

Circuit and taxonomy analysis. Minimum-weight connectivity over similarity graphs is the same computation whether the vertices are genes, documents, or network nodes.

Best Practices

• Confirm the graph is undirected before reaching for an MST algorithm. On a directed graph you need a minimum spanning arborescence (Chu-Liu/Edmonds), which is a different algorithm and not a small variation.
• Check connectivity and decide what “disconnected” should mean. Kruskal’s silently returns a forest; Prim’s silently returns the MST of one component. Neither failure is loud. Assert len(mst) == n - 1 or explicitly document that you want a forest.
• Break ties deterministically. Sorting (w, u, v) tuples rather than by weight alone makes the output reproducible. With distinct weights the MST is unique and this does not matter; with ties it very much does when tests compare exact edge sets.
• Pick the algorithm by density. prim_dense for E ≈ V², Kruskal’s or heap-Prim’s for sparse. On a V = 2000 complete graph, O(V²) = 4×10⁶ versus O(E log V) = 2×10⁶ × 11 ≈ 2×10⁷ — a 5x difference, plus the heap allocations.
• Exploit a cheap sort. If weights are small integers, counting-sort the edges and Kruskal’s drops to effectively O(E α(V)). If the edges arrive sorted (from a database ORDER BY, say), skip the sort entirely.
• Use path compression and union by size/rank together. Either alone gives O(log n); both together give inverse-Ackermann amortized. See ./16-disjoint-set-union-find.md.
• Do not use an MST when you actually need short paths. An MST minimizes total edge weight, not the distance between any particular pair — the two can differ by a factor of V. If node-to-node latency matters, you want a different topology.
• Do not add a constant to the weights hoping to change the answer — you cannot. The MST is invariant under any strictly increasing transform of the weights, because the algorithms only compare. (This is the opposite of the shortest-path case, where such a shift silently corrupts the answer.)
• For a maximum spanning tree, negate the weights rather than writing a second algorithm.
• Stop early once n − 1 edges are taken. On a graph with many redundant heavy edges, this cuts a substantial fraction of the work in Kruskal’s for one line of code.
• Watch memory in lazy Prim’s. The heap holds O(E) entries, not O(V). On a dense graph that is V² tuples, which in Python is not cheap; prim_dense is both faster and smaller there.
• Prefer heapq over a hand-rolled heap in production, but know its two limitations: no decrease-key (hence the stale-entry pattern) and it is a min-heap only (negate for max).

References

• roadmap.sh — Data Structures & Algorithms
• Minimum spanning tree — Wikipedia
• Spanning tree — Wikipedia
• Kruskal’s algorithm — Wikipedia
• Prim’s algorithm — Wikipedia
• Borůvka’s algorithm — Wikipedia
• Single-linkage clustering — Wikipedia
• Travelling salesman problem — Wikipedia
• cp-algorithms — Minimum spanning tree: Kruskal
• cp-algorithms — Kruskal with disjoint set union
• cp-algorithms — Minimum spanning tree: Prim
• cp-algorithms — Disjoint set union
• CLRS — Introduction to Algorithms, Chapter 23: Minimum Spanning Trees
• MIT 6.006 — Introduction to Algorithms (OpenCourseWare)
• VisuAlgo — Minimum spanning tree
• Python Documentation — heapq