Minimum spanning tree

Deep dive

How it works

In: undirected weighted graph as an edge list (u, v, w) over n vertices · Out: the V − 1 edges of least total weight (a forest if the graph is disconnected) and their total · State: none between calls; per call a union-find over the vertices · Cost: Kruskal O(E log E), dominated by the sort

1. Kruskal: sort the edges by weight.
2. For each edge (u, v), if find(u) ≠ find(v), add it and union(u, v). Stop after V − 1 edges.
3. Prim: start from any vertex. Keep a heap of edges leaving the tree.
4. Repeatedly add the lightest edge whose far end is not yet in the tree.
5. Borůvka: every component finds its lightest outgoing edge (one pass over all edges).
6. Add all those edges and merge the components. Each round at least halves the number of components, so there are at most log₂ V rounds. The per-round scan is embarrassingly parallel.

cut property: S | V−S        cycle property: the heaviest edge on any cycle
   a ─1─ b                    is in no MST (with distinct weights)
   │     │   lightest crossing edge (1) is safe to add
   4     3

Code

#[derive(Clone, Copy)]
pub struct Edge { pub u: u32, pub v: u32, pub w: u32 }

struct Dsu { p: Vec<u32>, sz: Vec<u32> }
impl Dsu {
    fn new(n: usize) -> Self { Dsu { p: (0..n as u32).collect(), sz: vec![1; n] } }
    fn find(&mut self, mut x: u32) -> u32 {
        while self.p[x as usize] != x { let g = self.p[self.p[x as usize] as usize]; self.p[x as usize] = g; x = g; }
        x
    }
    fn union(&mut self, a: u32, b: u32) -> bool {
        let (mut a, mut b) = (self.find(a), self.find(b));
        if a == b { return false; }
        if self.sz[a as usize] < self.sz[b as usize] { std::mem::swap(&mut a, &mut b); }
        self.p[b as usize] = a;
        self.sz[a as usize] += self.sz[b as usize];
        true
    }
}

/// Kruskal. Returns (total weight, indices of the chosen edges). A forest if the graph is disconnected.
pub fn kruskal(n: usize, edges: &[Edge]) -> (u64, Vec<usize>) {
    let mut order: Vec<usize> = (0..edges.len()).collect();
    order.sort_unstable_by_key(|&i| (edges[i].w, i)); // index tie-break: deterministic MST
    let mut dsu = Dsu::new(n);
    let (mut total, mut tree) = (0u64, Vec::with_capacity(n.saturating_sub(1)));
    for i in order {
        let e = edges[i];
        if dsu.union(e.u, e.v) {
            total += e.w as u64;
            tree.push(i);
            if tree.len() + 1 == n { break; } // spanning tree complete
        }
    }
    (total, tree)
}

/// Borůvka. Each round: every component picks its lightest outgoing edge, all are merged.
/// Ties are broken by edge index, so all picks are consistent and no cycle can form.
pub fn boruvka(n: usize, edges: &[Edge]) -> (u64, Vec<usize>) {
    let mut dsu = Dsu::new(n);
    let (mut total, mut tree) = (0u64, Vec::new());
    loop {
        let mut best = vec![usize::MAX; n]; // per component root: index of its lightest edge
        let better = |i: usize, j: usize| j == usize::MAX || (edges[i].w, i) < (edges[j].w, j);
        for (i, e) in edges.iter().enumerate() {
            let (a, b) = (dsu.find(e.u), dsu.find(e.v));
            if a == b { continue; }
            if better(i, best[a as usize]) { best[a as usize] = i; }
            if better(i, best[b as usize]) { best[b as usize] = i; }
        }
        let mut merged = false;
        for r in 0..n {
            let i = best[r];
            if i != usize::MAX && dsu.union(edges[i].u, edges[i].v) { // the same edge may be picked twice
                total += edges[i].w as u64;
                tree.push(i);
                merged = true;
            }
        }
        if !merged { return (total, tree); } // no component has an outgoing edge
    }
}

Complexity and constants

• Kruskal: sort O(E log E), then E near-constant finds. For 10⁸ edges of 12 B, the sort (~1.2 GB) dominates. A parallel or radix sort is the main lever.
• Prim with a binary heap: O(E log V). On dense graphs (E ≈ V²), the array version without a heap is O(V²) and wins.
• Borůvka: at most ⌈log₂ V⌉ rounds, each O(E α(V)). Contracting the edge list between rounds (dropping internal edges) makes later rounds much cheaper.
• Randomized linear time exists (Karger-Klein-Tarjan, expected O(E)) but is rarely faster in practice than a tuned Kruskal or Filter-Kruskal.

Efficiency

• Cost: measured with the code above on an Apple M4 Pro, one thread, random graph with 2^20 vertices and 4 · 2^20 edges, weights below 10^6, best of 3: Kruskal 259 ms, of which sorting the index array takes 168 ms (65 %); Borůvka 478 ms (no edge-list contraction). Memory: 12 B per edge plus an 8 B index per edge. Bound: the sort (memory bandwidth and cache misses).
• Levers:
  • pack (w << 32) | index into one u64 and sort plain integers — 1.8× (144 vs 259 ms, same tree weight; measured) — integer weights below 2^32
  • radix sort instead of comparison sort — near-linear sort (Key facts, not measured here) — integer weights
  • Filter-Kruskal — several times faster than plain Kruskal on dense or random graphs (Osipov et al. 2009; Implementation notes) — E far above V
  • stop after V − 1 edges — skips the remaining sorted edges (code above) — connected graphs
  • Borůvka with contraction of the edge list — later rounds much cheaper, scans parallelize (Complexity and constants) — multicore and GPU
• Naive → standard → state of the art:
  • Kruskal with a sorted index array · 259 ms (graph above)
  • Kruskal with packed u64 keys · 144 ms
  • Filter-Kruskal, parallel Borůvka-Kruskal hybrids · several times faster than plain Kruskal (Osipov et al. 2009)

Implementation notes

• Filter-Kruskal: quicksort-style partition around a pivot weight. Recurse on the light half first, then filter the heavy half by dropping edges whose endpoints are already connected. Most heavy edges are never sorted. Typically several times faster than plain Kruskal on dense or random graphs.
• Euclidean MST (points in the plane): build the Delaunay triangulation first (O(n log n), about 3n edges). The MST is a subgraph of it, so you avoid the n² complete graph. In higher dimensions use k-NN graphs or well-separated pair decompositions (approximate).
• Single-linkage clustering: run Kruskal and record each successful union with its weight. That sequence is the dendrogram.
• Pack edges as u64 keys (w << 32) | index to sort plain integers instead of structs.
• Max spanning tree: sort descending, or negate the weights.

Pitfalls

• Running Prim or Kruskal on a directed graph. The directed analogue (minimum arborescence) needs Chu-Liu/Edmonds.
• Assuming a single tree: check tree.len() == n - 1 before treating the result as spanning.
• Borůvka with equal weights and no consistent tie-break: two components can each pick a different edge of equal weight between them, which creates a cycle (the DSU above would skip it, but a naive "add all picked edges" version doesn't).
• Overflow: sum weights in u64.
• Using an MST as a routing tree and expecting short paths: the diameter of an MST can be Θ(V) even when the graph diameter is small.

Variants and alternatives

In production

Network design and clustering: SciPy minimum_spanning_tree and scipy.cluster.hierarchy single linkage, HDBSCAN (mutual-reachability MST; Campello et al. 2013). Image segmentation: scikit-image felzenszwalb (Kruskal-style merging) and the Felzenszwalb segmentation in OpenCV's ximgproc module (Felzenszwalb, Huttenlocher 2004). Chip design: Prim-Dijkstra routing trees (Alpert et al. 1995). Libraries: Boost Graph Library (Kruskal, Prim), petgraph (min_spanning_tree), NetworkX.

Implementations

Sources

• O. Borůvka, O jistém problému minimálním, Práce Moravské přírodovědecké společnosti, 1926.
• J. Kruskal, On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem, Proceedings of the AMS, 1956. paper
• R. Prim, Shortest Connection Networks and Some Generalizations, Bell System Technical Journal, 1957. paper
• D. Karger, P. Klein, R. Tarjan, A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees, JACM, 1995. paper
• V. Osipov, P. Sanders, J. Singler, The Filter-Kruskal Minimum Spanning Tree Algorithm, ALENEX, 2009. paper
• P. Felzenszwalb, D. Huttenlocher, Efficient Graph-Based Image Segmentation, IJCV, 2004. paper
• J. Gower, G. Ross, Minimum Spanning Trees and Single Linkage Cluster Analysis, Applied Statistics 18(1), 1969. paper
• C. Alpert, T. Hu, J. Huang, A. Kahng, D. Karger, Prim-Dijkstra Tradeoffs for Improved Performance-Driven Routing Tree Design, IEEE TCAD 14(7), 1995. paper