5 min read
On this page

Minimum Spanning Trees

A minimum spanning tree (MST) of a connected, weighted, undirected graph is a spanning tree with the smallest total edge weight. MST algorithms are fundamental to network design and clustering.

Properties

Cut Property

For any cut (partition of vertices into two non-empty sets), the lightest edge crossing the cut is in every MST (assuming unique edge weights).

Proof: Assume the lightest crossing edge e is not in MST T. T has some other edge e' crossing the same cut. Adding e to T creates a cycle crossing the cut. Removing e' breaks the cycle and gives a lighter spanning tree. Contradiction. ∎

Cycle Property

For any cycle in the graph, the heaviest edge in the cycle is NOT in any MST (assuming unique edge weights).

Proof: If the heaviest edge e were in MST T, removing e splits T into two components. Some other edge e' in the cycle connects these components with lighter weight. Adding e' and removing e gives a lighter spanning tree. Contradiction. ∎

Uniqueness

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

If some weights are equal, there may be multiple MSTs, but the multiset of edge weights is the same in every MST.

Kruskal's Algorithm

Greedy by edge weight: Sort edges, add each edge if it doesn't create a cycle.

FUNCTION KRUSKAL(n, edges)
    SORT edges BY weight
    uf ← new UNION_FIND(n)
    mst ← empty list
    total ← 0

    FOR EACH (w, u, v) IN edges
        IF FIND(uf, u) ≠ FIND(uf, v)
            UNION(uf, u, v)
            APPEND (w, u, v) TO mst
            total ← total + w
            IF length(mst) = n - 1 THEN BREAK
    RETURN (total, mst)

Time: O(E log E) for sorting + O(E α(V)) for union-find ≈ O(E log E).

Best for: Sparse graphs, edge list input, when edges are already sorted.

Correctness

Each added edge is the lightest edge crossing some cut (the cut between the two components being joined). By the cut property, it belongs to the MST.

Prim's Algorithm

Greedy by closest vertex: Grow the MST from a starting vertex, always adding the lightest edge connecting the tree to a non-tree vertex.

FUNCTION PRIM(graph)
    n ← number of vertices
    in_mst ← array of size n, all false
    heap ← MIN_HEAP containing (0, vertex 0)
    total ← 0
    count ← 0

    WHILE heap is not empty
        (w, u) ← EXTRACT_MIN(heap)
        IF in_mst[u] THEN CONTINUE
        in_mst[u] ← true
        total ← total + w
        count ← count + 1
        IF count = n THEN BREAK

        FOR EACH (v, weight) IN neighbors of u
            IF NOT in_mst[v]
                INSERT (weight, v) INTO heap
    RETURN total

| Implementation | Time | |---|---| | Array (no heap) | O(V²) | | Binary heap | O((V + E) log V) | | Fibonacci heap | O(E + V log V) |

Best for: Dense graphs (with array implementation), adjacency list input.

Correctness

At each step, the added edge is the lightest crossing the cut between the tree and non-tree vertices. By the cut property, it's in the MST.

Borůvka's Algorithm

Parallel-friendly: In each round, every component finds its lightest outgoing edge and adds it.

1. Initialize: each vertex is its own component.
2. Repeat until one component:
   a. For each component, find the lightest edge leaving it.
   b. Add all such edges (contracting components).

Time: O(E log V). Each round at least halves the number of components → at most O(log V) rounds, each taking O(E).

Best for: Parallel/distributed computation (each component can be processed independently). Also used as a building block in faster MST algorithms.

Steiner Tree Problem

Given a graph and a subset of terminal vertices, find the minimum-weight tree connecting all terminals (may include non-terminal vertices as intermediate nodes).

Difference from MST: MST connects ALL vertices. Steiner tree connects only the terminals.

Complexity: NP-hard (unlike MST). No known polynomial algorithm.

Approximation: The MST of the terminals' complete graph (with distances = shortest paths) gives a 2-approximation. Better approximations exist (1.39-approximation by Byrka et al.).

Applications: VLSI routing, network design, phylogenetics.

Minimum Bottleneck Spanning Tree

Minimize the maximum edge weight (bottleneck) rather than the total weight.

Theorem: Every MST is a minimum bottleneck spanning tree (but not vice versa).

So computing the MST also solves the bottleneck problem. The maximum edge in the MST is the bottleneck.

Minimax path: The path between u and v in the MST minimizes the maximum edge weight among all u-v paths.

Second-Best MST

The spanning tree with the second-smallest total weight.

Algorithm:

  1. Compute the MST.
  2. For each non-MST edge (u, v), adding it creates a cycle. The second-best MST is obtained by replacing the heaviest edge on the MST path from u to v with (u, v).
  3. Try all non-MST edges, keep the best replacement.

Time: O(V² + E) with LCA (Lowest Common Ancestor) preprocessing for path maximum queries.

Dynamic MST

Maintain an MST as edges are inserted or deleted.

Fully dynamic: O(√E) per operation (Holm, de Lichtenberg, Thorup). Complex.

Semi-dynamic (insertions only): Much simpler. Add the edge; if it creates a cycle, remove the heaviest edge in the cycle.

Relationship to Other Problems

  • Clustering: MST-based clustering: build MST, remove the k-1 heaviest edges to get k clusters (single-linkage clustering).
  • Shortest path tree: Not the same as MST. Shortest path tree minimizes distance from a source. MST minimizes total edge weight.
  • Traveling Salesman: MST weight ≤ TSP tour weight ≤ 2 × MST weight (for metric TSP). MST is a lower bound on TSP.

Applications in CS

  • Network design: Connect all nodes with minimum cable/cost. Telecommunications, power grids, water supply.
  • Cluster analysis: Single-linkage hierarchical clustering = build MST, then cut edges.
  • Image segmentation: Build a graph of pixels, MST-based segmentation (Felzenszwalb's algorithm).
  • Approximation algorithms: MST is used as a subroutine in TSP approximation (Christofides), Steiner tree approximation, and other problems.
  • Maze generation: Random MST of a grid = a random maze (Kruskal's or Prim's with random weights).
  • Network analysis: MST reveals the "backbone" of a network — the most important connections.
  • Phylogenetics: Minimum spanning trees approximate evolutionary relationships.