309. Min Spanning Tree

Given a connected, undirected, weighted graph, find a spanning tree (acyclic connected subgraph touching every vertex) of minimum total edge weight.

309.1. Two classic algorithms

Kruskal’s algorithm (1956): edge-based,

Sort edges by weight ascending
Initialize T = empty (every node is its own component)
For each edge (u, v) in sorted order:
    If u and v are in different components:
        Add (u, v) to T
        Merge their components
Return T

Prim’s algorithm (1957): vertex-based, with binary heap, with Fibonacci heap

Initialize T = {arbitrary starting vertex}
While T doesn't span the graph:
    Find min-weight edge (u, v) with u ∈ T, v ∉ T
    Add v and edge (u, v) to T
Return T

309.2. Why it’s MST (correctness)

The cut property: for any cut of the graph, the minimum-weight edge crossing the cut belongs to some MST. Both Kruskal and Prim repeatedly select such cut-crossing minimum edges.

The cycle property: for any cycle, the maximum-weight edge does not belong to any MST. (Kruskal implicitly enforces this by skipping cycle-creating edges.)

309.3. Properties

• Unique MST iff all edge weights are distinct
• Tree: edges, no cycles
• Total weight: sum of MST edges; minimum among all spanning trees
• Multiple MSTs: with ties, any choice that breaks cycles consistently gives the same total weight

309.4. Where it shows up

• Network design: minimum-cost wiring / connection (telephone, power, road)
• Clustering: single-linkage clustering = MST then prune longest edges
• Approximation algorithms: 2-factor approx for metric TSP uses MST traversal; Christofides is more refined
• Image segmentation: graph cuts based on MST

309.5. Comparison

309.6. See also

• TSP — uses MST in lower bounds & approximations
• Floyd-Warshall — all-pairs shortest path (related)
• Dijkstra — single-source shortest path (related, different structure)