On this page

Minimum Spanning Trees: Kruskal, Prim & Borůvka

Why this exists

You must connect sites — towns to an electricity grid, servers in a data centre, houses to a water main — and you know the cost of building a link between each pair that can be linked. Every site must be reachable from every other, and you want to spend as little as possible. Any cheapest solution contains no cycle (dropping one edge of a cycle keeps everything connected and saves money, assuming positive costs), so it is a tree that touches every site: a minimum spanning tree (MST).

The problem is old and practical. In 1926 the Czech mathematician Otakar Borůvka, asked by a friend at the West Moravian power company how to wire up southern Moravia economically, published the first MST algorithm. Vojtěch Jarník gave a second one in 1930; it was rediscovered by Robert Prim at Bell Labs (1957, for telephone networks) and by Edsger Dijkstra (1959), which is why it carries Prim's name. Joseph Kruskal published the sort-and-join algorithm in 1956. All three are greedy, all three are correct for the same reason — the cut property — and all three run in . The rest of the story is theoretical: Fredman and Tarjan's Fibonacci heaps (1987) give Prim ; Karger, Klein and Tarjan (1995) found a randomized algorithm with expected time; Chazelle (2000) gave a deterministic bound; and Pettie and Ramachandran (2002) gave a provably optimal deterministic algorithm whose running time is still unknown — it is somewhere between linear and Chazelle's bound.

MSTs matter beyond network design because the tree encodes the graph's "cheapest connectivity" in a way many other problems inherit. The MST minimizes the largest edge on every path (bottleneck paths). Deleting its heaviest edges gives the optimal -clustering by spacing. Doubling it gives a 2-approximate travelling-salesman tour. Running Kruskal with a different merge test segments images. The MST section of Greedy Algorithms and the Graphs overview show the basic Kruskal and Prim code; this lesson proves why they work, traces them by hand, adds Borůvka, and covers the variants and applications. It builds directly on Union-Find in Depth (Kruskal's engine) and Heaps & Priority Queues (Prim's engine).

Pattern triggers

If the problem says or has…Think of…
"connect all … with minimum total cost", "every node reachable", undirected costsMST (Kruskal or Prim)
Points in the plane, cost = distance between every pairDense graph: array Prim; Euclidean: Delaunay + Kruskal
Cost = Manhattan distance, up to Manhattan MST (octant candidate edges)
"you may also build a well / power plant at a node for cost "Virtual node 0 joined to every node with weight , then MST
"minimize the maximum edge on the path", "minimize the largest step"Minimum bottleneck path: path in the MST, or Kruskal until connected
Split points into groups maximizing the minimum gap between groupsKruskal stopped at components (single-linkage clustering)
"which edges are in every MST / in some MST / in no MST?"Cut and cycle properties, Kruskal processing equal-weight groups together
"next-cheapest network", "if this link fails…"Second-best MST: swap one non-tree edge for the max edge on its tree path
"maximize the total weight of a spanning tree", "most reliable network"Maximum spanning tree (sort descending, or negate)
Edge weights are XOR / some function of node labels, is hugeBorůvka: only "cheapest edge out of each component" is needed per round
Directed edges, all nodes reachable from a root, min total costNot MST — minimum arborescence (Chu–Liu/Edmonds)
"connect only these terminals", may use other nodesNot MST — Steiner tree (NP-hard); MST over terminal distances is a 2-approximation
"shortest path from the source to each node"Not MST — shortest-path tree (Dijkstra)

The meta-trigger: undirected, connect everything, minimize the sum (or the maximum) of edge weights, no constraint on path lengths. The last three rows are the classic look-alikes; an interviewer who asks for "the cheapest way for the root to reach everyone along shortest paths" wants Dijkstra, not Prim.

Intuition & first principles

Definitions

Let be a connected, undirected graph with real edge weights . A spanning tree is a subset that connects all vertices and has no cycle. Basic tree facts, all provable by induction:

  • a spanning tree has exactly edges;
  • adding any non-tree edge to creates exactly one cycle: plus the unique tree path from to ;
  • removing any edge of that cycle gives another spanning tree.

A minimum spanning tree minimizes . If is disconnected there is no spanning tree; the analogous object is a minimum spanning forest, one MST per component, which Kruskal and Borůvka compute naturally.

A cut is a partition of the vertices into two non-empty sides. An edge crosses the cut if its endpoints are on different sides. A light edge for a cut is a crossing edge of minimum weight.

The two properties every MST algorithm rests on

flowchart LR
    subgraph S["side S"]
        a((a)) --- b((b))
        b --- c((c))
    end
    subgraph R["side V minus S"]
        x((x)) --- y((y))
        y --- z((z))
    end
    b ===|"light edge e, weight 2"| x
    c -.-|"crossing edge f, weight 5"| z
    a -.-|"crossing edge g, weight 9"| y

Cut property. For any cut, if is the unique lightest edge crossing it, then belongs to every MST. (With ties: some light edge belongs to some MST — more precisely, any light edge can be added to any set of edges that is contained in some MST and does not cross the cut.)

Cycle property. For any cycle, if is the unique heaviest edge on it, then belongs to no MST.

The intuition: across any border, the cheapest crossing is always worth taking — you need some crossing, and swapping any other for the cheapest can only save money. And on any loop, the most expensive link is never needed — the rest of the loop already provides an alternative route. Kruskal and Prim apply the cut property; the "reverse-delete" algorithm applies the cycle property. The proofs are in the Correctness section; they are short exchange arguments of the same shape as the ones in Greedy Algorithms.

Why greedy works here when it fails elsewhere

Greedy algorithms usually fail because an early cheap choice blocks a better later one. Spanning trees have special structure — they are the bases of a graphic matroid — and on any matroid, "take the best element that keeps the set independent" is optimal. "Independent" here means "acyclic". You do not need matroid theory to use MSTs, but it explains why the same greedy idea works for MSTs and fails for, say, shortest Hamiltonian paths: a set of edges that forms a Hamiltonian path is not a matroid basis.

Mechanics

The running example: 7 vertices, 12 edges, all weights distinct (so the MST is unique — proved below). The MST, computed by all three algorithms and by brute force over all 308 spanning trees of this graph, has weight 35. Thick edges are the MST.

flowchart LR
    A((A)) ===|"7"| B((B))
    A ===|"5"| D((D))
    B ---|"8"| C((C))
    B ---|"9"| D
    B ===|"4"| E((E))
    C ===|"3"| E
    D ---|"12"| E
    D ===|"6"| F((F))
    E ---|"11"| F
    E ===|"10"| G((G))
    F ---|"13"| G
    C ---|"14"| G

MST edges: C–E 3, B–E 4, A–D 5, D–F 6, A–B 7, E–G 10. Total .

Kruskal: sort the edges, join forests

  1. Sort all edges by weight.
  2. Start with a forest of single-vertex trees (a DSU with every vertex its own set).
  3. Scan edges in order. For edge : if find(u) != find(v), accept it and union(u, v); otherwise reject it — it would close a cycle.
  4. Stop after accepted edges (or when the edges run out: then the graph is disconnected and you have a minimum spanning forest).

Each accepted edge is the lightest edge crossing the cut between its endpoint's component and everything else — that is the cut property, applied times.

Kruskal takes edges cheapest first and skips any whose endpoints are already connected, stopping once it has V − 1 edges.

Trace. Generated by scripts/traces/kruskal.py, the same run as the visualizer (union by size, path halving; a tie in size keeps the first root).

StepEdge (weight)find(u), find(v)DecisionTree weightComponents
0——sort 12 edges07
1C–E (3)C, Eaccept36
2B–E (4)B, Caccept75
3A–D (5)A, Daccept124
4D–F (6)A, Faccept183
5A–B (7)A, Caccept252
6B–C (8)A, Areject (cycle B–E–C)252
7B–D (9)A, Areject (cycle B–A–D)252
8E–G (10)A, Gaccept, 6 edges: stop351

The four heaviest edges (11, 12, 13, 14) are never examined. The early exit does not change the asymptotic cost — the sort already took — but in practice it skips the tail of the edge list.

Prim: grow one tree from a root

  1. Start with any vertex in the tree.
  2. Repeatedly add the lightest edge with exactly one endpoint in the tree, together with its other endpoint.
  3. Stop when all vertices are in the tree.

Each step applies the cut property to the cut (tree, rest). The question is how to find "the lightest edge leaving the tree" fast. Two heap-based ways:

  • Lazy Prim pushes every edge leaving each newly added vertex onto a min-heap of edges. When an edge is popped, if both endpoints are already in the tree it is stale — discard it. The heap holds up to entries: time, extra space. Simple, and the standard choice in contests.
  • Eager Prim keeps, for each vertex outside the tree, key[v] = the lightest known edge from the tree to , in an indexed priority queue with decrease-key. Exactly one heap entry per vertex: time, heap space. This is Dijkstra's algorithm with key[v] = w(u, v) instead of dist[u] + w(u, v).
flowchart TD
    P0["tree = {s}, push edges of s"] --> P1{"heap empty or<br/>tree has V vertices?"}
    P1 -->|"yes"| P9["done: tree edges form the MST"]
    P1 -->|"no"| P2["pop lightest edge (w, u, v)"]
    P2 --> P3{"v already in tree?"}
    P3 -->|"yes: stale"| P1
    P3 -->|"no"| P4["add v and edge (u, v)<br/>push every edge (v, x) with x outside"]
    P4 --> P1

Trace: lazy Prim from A. Heap entries are (weight, from, to); the heap column lists its contents after the step, lightest first.

StepPoppedActionTree verticesWeightHeap after the step
0—start at A, push A's edgesA05 A–D, 7 A–B
15 A–Dadd DA D56 D–F, 7 A–B, 9 D–B, 12 D–E
26 D–Fadd FA D F117 A–B, 9 D–B, 11 F–E, 12 D–E, 13 F–G
37 A–Badd BA D F B184 B–E, 8 B–C, 9 D–B, 11 F–E, 12 D–E, 13 F–G
44 B–Eadd E+ E223 E–C, 8 B–C, 9 D–B, 10 E–G, 11 F–E, 12 D–E, 13 F–G
53 E–Cadd C+ C258 B–C, 9 D–B, 10 E–G, 11 F–E, 12 D–E, 13 F–G, 14 C–G
68 B–Cstale (C in tree)—259 D–B, 10 E–G, …
79 D–Bstale (B in tree)—2510 E–G, 11 F–E, …
810 E–Gadd G: 7 vertices, stopall3511 F–E, 12 D–E, 13 F–G, 14 C–G (never popped)

Prim adds the edges in the order 5, 6, 7, 4, 3, 10 — a different order from Kruskal (3, 4, 5, 6, 7, 10) but the same tree, as it must be when the MST is unique. Notice the non-monotone weights: Prim can only take B–E (4) after B is in the tree.

Eager Prim's key array on the same graph (∞ = no known edge yet; the picked vertex is the one with the smallest key):

Pickkey[B]key[C]key[D]key[E]key[F]key[G]
A7∞5∞∞∞
D7∞—126∞
F7∞—11—13
B—8—4—13
E—3———10
C—————10
G——————

The keys only ever decrease: key[E] goes 12 → 11 → 4, key[C] goes 8 → 3, key[G] goes 13 → 10. Those are the decrease-key operations.

The array version. Drop the heap: store key[] in a plain array and find the minimum by scanning all entries. Each of the iterations costs for the scan plus for relaxations: . On a dense graph (, for example all pairs of points) this beats the heap's , needs no adjacency list at all (compute weights on the fly), and has excellent constants. For points it is 25 million simple steps.

Borůvka: every component grabs its cheapest edge

  1. Start with every vertex as its own component.
  2. In each round, for every component, find the lightest edge leaving it. Add all of those edges at once (skipping one that a union in this round already made redundant).
  3. Repeat until one component remains (or no component has an outgoing edge).

Every component adds at least one edge per round, and each added edge merges at least two components, so the number of components at least halves each round: at most rounds, each with a DSU. Total .

Trace on the example, ties broken by edge index (none occur here — weights are distinct):

RoundComponents beforeCheapest edge out of eachEdges addedComponents afterWeight
1{A} {B} {C} {D} {E} {F} {G}A: A–D 5, B: B–E 4, C: C–E 3, D: A–D 5, E: C–E 3, F: D–F 6, G: E–G 10C–E 3, B–E 4, A–D 5, D–F 6, E–G 10{A, D, F} {B, C, E, G}28
2{A, D, F} {B, C, E, G}both: A–B 7A–B 7{A … G}35

Two rounds for seven vertices. Round 1 picks five distinct edges (A and D chose the same one; so did C and E).

flowchart LR
    R0["round 0<br/>7 components"] -->|"5 cheapest edges"| R1["round 1<br/>{A, D, F}, {B, C, E, G}"]
    R1 -->|"A-B weight 7"| R2["round 2<br/>1 component, weight 35"]

Borůvka matters for three reasons. Its rounds are embarrassingly parallel — every component's search is independent — so it is the basis of parallel and distributed MST algorithms (GPU MST codes, the GHS distributed algorithm of Gallager, Humblet and Spira, 1983). It needs only "cheapest edge out of a component", which can sometimes be computed without listing all edges (XOR-MST: a trie answers it). And it is the first phase of the Karger–Klein–Tarjan linear-time algorithm.

Ties in Borůvka

If two edges of equal weight leave a component and different components pick different ones, adding all chosen edges at once can close a cycle: with three components joined pairwise by edges of weight 1, each may pick a different edge and the three picks form a triangle. Break ties consistently — compare (weight, edge index) — so that "lightest" is a strict total order. Kruskal and Prim do not have this problem because they add one edge at a time and check.

The ladder: brute force → better → optimal

Rung 1: enumerate all spanning trees

Try every subset of edges, keep those that are acyclic, take the cheapest. There are subsets — for the example, of which 308 are spanning trees. A complete graph has spanning trees (Cayley's formula): 16,807 for , about for . Correct, and useful only as a test oracle (the verification for this page used exactly that).

Rung 2: Kruskal with a naive cycle check

Sort the edges, and for each edge run a DFS in the current forest to see whether already reaches . Correct (it is Kruskal), but each check costs : . It improves on brute force from exponential to polynomial, because the cut property tells us we never need to reconsider a choice.

Rung 3: Kruskal with union-find

Replace the DFS by find(u) == find(v): for sorting plus for the DSU. Since , , so this is . If edges are already sorted, or weights are small integers (counting/radix sort, see Non-Comparison Sorts), Kruskal becomes — essentially linear.

Rung 4: Prim with a heap

with a binary heap (lazy or eager), with a Fibonacci heap (decrease-key amortized ). No sorting of all edges up front, and it works directly on an adjacency list. On dense graphs, the array version at is optimal (you must look at every edge).

Rung 5: Borůvka and beyond

Borůvka is like the others but parallel. Combining Borůvka rounds with Prim (run Borůvka until components are large, then Prim on the contracted graph) gives . The randomized Karger–Klein–Tarjan algorithm achieves expected using random sampling and linear-time MST verification. These are of theoretical interest; in practice Kruskal and Prim with binary heaps win on constants.

RungTimeExtra spaceBest when
Brute force over subsetstest oracle for
Kruskal + DFS cycle checknever
Kruskal + DSU; if presorted + edge listsparse graphs, edge lists, offline sweeps
Lazy Prim, binary heapadjacency lists, simple code
Eager Prim, indexed heapadjacency lists, memory-tight
Prim, Fibonacci heaptheory; rarely faster in practice
Prim, plain arraydense / complete graphs, points
Borůvka + DSUparallel, distributed, implicit edges
Karger–Klein–Tarjan expectedtheory

Correctness

Proof of the cut property

Claim. Let be a cut and a crossing edge that is strictly lighter than every other crossing edge. Then every MST contains .

Proof (exchange). Suppose an MST does not contain . Adding to creates exactly one cycle. That cycle crosses the cut at and, since it returns to its starting side, must cross it again at some other edge . Remove : is again a spanning tree (we removed an edge from the only cycle). Its weight is , since . That contradicts the minimality of .

With ties () the same exchange gives , so is also an MST, and it contains . The general form used by algorithms (CLRS calls it the safe edge theorem): if is a subset of some MST, and the cut respects (no edge of crosses it), then adding any light edge of the cut to keeps it a subset of some MST. The proof is the same exchange, choosing on the cycle outside — possible because crosses the cut and has no crossing edges.

Proof of the cycle property

Claim. Let be a cycle and the unique heaviest edge on . Then no MST contains .

Proof. Suppose MST contains . Removing splits into two components, defining a cut. The rest of the cycle connects the endpoints of , so it contains another edge crossing this cut. is a spanning tree with . Contradiction.

Uniqueness when weights are distinct

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

Proof. Suppose are both MSTs. Let be the lightest edge in their symmetric difference; say . Adding to creates a cycle, which must contain some edge (otherwise would contain the whole cycle). is in the symmetric difference, so (distinct weights, and was the lightest there). Then is a spanning tree lighter than . Contradiction.

The converse fails: a graph with repeated weights can still have a unique MST (for example, if the graph is itself a tree). What repeated weights can do is produce several MSTs — all with the same total weight, and, a useful fact, the same multiset of edge weights.

Kruskal is correct

Invariant: the accepted edges are always a subset of some MST.

Initially . When Kruskal accepts , and are in different DSU components; let be 's component. The cut respects (no accepted edge leaves a component). Every edge crossing it is unprocessed — any already-processed crossing edge would have been accepted and merged its endpoints' components, contradicting that it still crosses. Since edges are processed in sorted order, is a light edge of the cut. By the safe edge theorem, is a subset of some MST. Rejected edges have both endpoints in one component, so adding them would create a cycle; they are in no spanning tree that contains . At the end has edges and is contained in an MST, so it is an MST.

Prim is correct

Invariant: the tree edges so far are a subset of some MST. Each step takes a light edge of the cut (tree vertices, the rest), which respects the current tree edges, so the safe edge theorem applies. In lazy Prim, stale edges are exactly the ones whose both endpoints are in the tree; discarding them never discards a crossing edge.

Borůvka is correct

With a strict total order on edges (weight, then index), each component's chosen edge is the unique lightest edge leaving it, so by the cut property it belongs to the unique MST under that order. All chosen edges in a round therefore belong to one MST, so adding them all together cannot create a cycle. Without the tie-break, two components may choose different equal-weight edges that together with the tree close a cycle — that is the failure mode the warning above describes.

Reverse-delete is correct

Sort edges in decreasing order and delete each edge if the graph stays connected without it. Each deleted edge is the heaviest on some cycle (the cycle it closed with the remaining graph), so the cycle property says it is in no MST. This is the mirror image of Kruskal; it is slower ( connectivity checks) but sometimes convenient in proofs.

Complexity

AlgorithmTimeSpaceNotes
Kruskal DSU + edge listSort dominates; DSU is
Lazy Prim (binary heap) heapUp to stale entries
Eager Prim (indexed heap) extract-min, decrease-key
Prim (Fibonacci heap)Large constants
Prim (array)Optimal for dense graphs
Borůvka rounds of

Best, average and worst cases coincide asymptotically for all of these; only early termination in Kruskal and the number of stale pops in lazy Prim vary with the input.

Constants and memory. Kruskal's sort is a cache-friendly sequential pass over a contiguous array of edges, followed by DSU operations that are random accesses into a -sized array — fine while fits in cache. Lazy Prim's heap of edges can grow to entries, which for is hundreds of megabytes in Java objects; store edges in primitive arrays or use eager Prim. The array Prim touches keys per iteration sequentially and vectorizes well. For graphs too large for memory (billions of edges), MSTs are computed with external-memory Kruskal (sort on disk, DSU in memory if fits) or with distributed Borůvka rounds.

Implementation

Kruskal with union-find

The same tests in all four languages: the example graph (vertices A–G as 0–6), total 35 and the exact edge set; a disconnected graph that must be reported; and a 4-cycle with equal weights.

def kruskal(n: int, edges: list[tuple[int, int, int]]) -> tuple[int, list[tuple[int, int, int]]] | None:
    """edges: (u, v, w). Returns (total weight, tree edges) or None if disconnected."""
    parent = list(range(n))
    size = [1] * n

    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]          # path halving
            x = parent[x]
        return x

    tree: list[tuple[int, int, int]] = []
    total = 0
    for u, v, w in sorted(edges, key=lambda e: e[2]):
        ru, rv = find(u), find(v)
        if ru == rv:
            continue                               # would close a cycle
        if size[ru] < size[rv]:
            ru, rv = rv, ru
        parent[rv] = ru
        size[ru] += size[rv]
        tree.append((u, v, w))
        total += w
        if len(tree) == n - 1:
            break
    return (total, tree) if len(tree) == n - 1 else None


def main() -> None:
    A, B, C, D, E, F, G = range(7)
    edges = [(A, B, 7), (A, D, 5), (B, C, 8), (B, D, 9), (B, E, 4), (C, E, 3),
             (D, E, 12), (D, F, 6), (E, F, 11), (E, G, 10), (F, G, 13), (C, G, 14)]
    result = kruskal(7, edges)
    assert result is not None
    total, tree = result
    assert total == 35
    assert [w for _, _, w in tree] == [3, 4, 5, 6, 7, 10]
    assert {(min(u, v), max(u, v)) for u, v, _ in tree} == {(C, E), (B, E), (A, D), (D, F), (A, B), (E, G)}
    assert kruskal(4, [(0, 1, 1), (2, 3, 2)]) is None          # two components
    square = kruskal(4, [(0, 1, 1), (1, 2, 1), (2, 3, 1), (3, 0, 1)])
    assert square is not None and square[0] == 3                 # ties: any 3 edges
    assert kruskal(1, []) == (0, [])
    print("kruskal ok")


main()
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Kruskal {
    /** Returns the tree edges {u, v, w}, or null if the graph is disconnected. */
    static List<int[]> kruskal(int n, int[][] edges) {
        int[] parent = new int[n], size = new int[n];
        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
        int[][] sorted = edges.clone();
        Arrays.sort(sorted, (a, b) -> Integer.compare(a[2], b[2]));
        List<int[]> tree = new ArrayList<>();
        for (int[] e : sorted) {
            if (tree.size() == n - 1) break;
            int ru = find(parent, e[0]), rv = find(parent, e[1]);
            if (ru == rv) continue;                       // would close a cycle
            if (size[ru] < size[rv]) { int t = ru; ru = rv; rv = t; }
            parent[rv] = ru;
            size[ru] += size[rv];
            tree.add(e);
        }
        return tree.size() == n - 1 ? tree : null;
    }

    static int find(int[] parent, int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];                // path halving
            x = parent[x];
        }
        return x;
    }

    static long weight(List<int[]> tree) {
        long s = 0;
        for (int[] e : tree) s += e[2];
        return s;
    }

    static void check(boolean cond, String msg) {
        if (!cond) throw new AssertionError(msg);
    }

    public static void main(String[] args) {
        final int A = 0, B = 1, C = 2, D = 3, E = 4, F = 5, G = 6;
        int[][] edges = {{A, B, 7}, {A, D, 5}, {B, C, 8}, {B, D, 9}, {B, E, 4}, {C, E, 3},
                         {D, E, 12}, {D, F, 6}, {E, F, 11}, {E, G, 10}, {F, G, 13}, {C, G, 14}};
        List<int[]> tree = kruskal(7, edges);
        check(tree != null && weight(tree) == 35, "weight 35");
        int[] ws = tree.stream().mapToInt(e -> e[2]).toArray();
        check(Arrays.equals(ws, new int[]{3, 4, 5, 6, 7, 10}), "accepted weights");
        Set<String> got = new HashSet<>();
        for (int[] e : tree) got.add(Math.min(e[0], e[1]) + "-" + Math.max(e[0], e[1]));
        check(got.equals(Set.of(C + "-" + E, B + "-" + E, A + "-" + D, D + "-" + F, A + "-" + B, E + "-" + G)), "edge set");
        check(kruskal(4, new int[][]{{0, 1, 1}, {2, 3, 2}}) == null, "disconnected");
        List<int[]> sq = kruskal(4, new int[][]{{0, 1, 1}, {1, 2, 1}, {2, 3, 1}, {3, 0, 1}});
        check(sq != null && weight(sq) == 3, "square");
        check(kruskal(1, new int[0][]).isEmpty(), "single vertex");
        System.out.println("kruskal ok");
    }
}
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <optional>
#include <set>
#include <utility>
#include <vector>

using Edge = std::array<int, 3>;   // {u, v, w}

int find_root(std::vector<int>& parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];               // path halving
        x = parent[x];
    }
    return x;
}

// Returns the tree edges, or nullopt if the graph is disconnected.
std::optional<std::vector<Edge>> kruskal(int n, std::vector<Edge> edges) {
    std::vector<int> parent(n), size(n, 1);
    std::iota(parent.begin(), parent.end(), 0);
    std::sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) { return a[2] < b[2]; });
    std::vector<Edge> tree;
    for (const Edge& e : edges) {
        if (static_cast<int>(tree.size()) == n - 1) break;
        int ru = find_root(parent, e[0]), rv = find_root(parent, e[1]);
        if (ru == rv) continue;                      // would close a cycle
        if (size[ru] < size[rv]) std::swap(ru, rv);
        parent[rv] = ru;
        size[ru] += size[rv];
        tree.push_back(e);
    }
    if (static_cast<int>(tree.size()) != n - 1) return std::nullopt;
    return tree;
}

std::int64_t weight(const std::vector<Edge>& tree) {
    std::int64_t s = 0;
    for (const Edge& e : tree) s += e[2];
    return s;
}

int main() {
    enum { A, B, C, D, E, F, G };
    std::vector<Edge> edges = {{A, B, 7}, {A, D, 5}, {B, C, 8}, {B, D, 9}, {B, E, 4}, {C, E, 3},
                               {D, E, 12}, {D, F, 6}, {E, F, 11}, {E, G, 10}, {F, G, 13}, {C, G, 14}};
    auto tree = kruskal(7, edges);
    assert(tree && weight(*tree) == 35);
    std::vector<int> ws;
    for (const Edge& e : *tree) ws.push_back(e[2]);
    assert((ws == std::vector<int>{3, 4, 5, 6, 7, 10}));
    std::set<std::pair<int, int>> got;
    for (const Edge& e : *tree) got.insert({std::min(e[0], e[1]), std::max(e[0], e[1])});
    assert((got == std::set<std::pair<int, int>>{{C, E}, {B, E}, {A, D}, {D, F}, {A, B}, {E, G}}));
    assert(!kruskal(4, {{0, 1, 1}, {2, 3, 2}}).has_value());
    auto sq = kruskal(4, {{0, 1, 1}, {1, 2, 1}, {2, 3, 1}, {3, 0, 1}});
    assert(sq && weight(*sq) == 3);
    assert(kruskal(1, {}).value().empty());
    std::cout << "kruskal ok\n";
}
type Edge = [number, number, number]; // [u, v, w]

/** Returns the tree edges, or null if the graph is disconnected. */
function kruskal(n: number, edges: Edge[]): Edge[] | null {
  const parent = Array.from({ length: n }, (_, i) => i);
  const size = new Array<number>(n).fill(1);
  const find = (x: number): number => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]]; // path halving
      x = parent[x];
    }
    return x;
  };
  const tree: Edge[] = [];
  for (const e of [...edges].sort((a, b) => a[2] - b[2])) {
    if (tree.length === n - 1) break;
    let ru = find(e[0]), rv = find(e[1]);
    if (ru === rv) continue; // would close a cycle
    if (size[ru] < size[rv]) [ru, rv] = [rv, ru];
    parent[rv] = ru;
    size[ru] += size[rv];
    tree.push(e);
  }
  return tree.length === n - 1 ? tree : null;
}

function check(cond: boolean, msg: string): void {
  if (!cond) throw new Error(msg);
}

const [A, B, C, D, E, F, G] = [0, 1, 2, 3, 4, 5, 6];
const edges: Edge[] = [[A, B, 7], [A, D, 5], [B, C, 8], [B, D, 9], [B, E, 4], [C, E, 3],
  [D, E, 12], [D, F, 6], [E, F, 11], [E, G, 10], [F, G, 13], [C, G, 14]];
const tree = kruskal(7, edges);
check(tree !== null && tree.reduce((s, e) => s + e[2], 0) === 35, "weight 35");
check(tree!.map((e) => e[2]).join(",") === "3,4,5,6,7,10", "accepted weights");
const got = new Set(tree!.map(([u, v]) => `${Math.min(u, v)}-${Math.max(u, v)}`));
const want = [[C, E], [B, E], [A, D], [D, F], [A, B], [E, G]].map(([u, v]) => `${u}-${v}`);
check(got.size === 6 && want.every((k) => got.has(k)), "edge set");
check(kruskal(4, [[0, 1, 1], [2, 3, 2]]) === null, "disconnected");
const sq = kruskal(4, [[0, 1, 1], [1, 2, 1], [2, 3, 1], [3, 0, 1]]);
check(sq !== null && sq.reduce((s, e) => s + e[2], 0) === 3, "square");
check(kruskal(1, [])!.length === 0, "single vertex");
console.log("kruskal ok");

Lazy Prim with a binary heap

Same graph and expectations; additionally, Prim must return 35 from every start vertex.

import heapq


def prim(n: int, edges: list[tuple[int, int, int]], start: int = 0) -> int | None:
    """Lazy Prim. Returns the MST weight, or None if the graph is disconnected."""
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((w, v))
        adj[v].append((w, u))
    in_tree = [False] * n
    in_tree[start] = True
    heap = list(adj[start])
    heapq.heapify(heap)
    total, added = 0, 1
    while heap and added < n:
        w, v = heapq.heappop(heap)
        if in_tree[v]:
            continue                                 # stale entry
        in_tree[v] = True
        total += w
        added += 1
        for edge in adj[v]:
            if not in_tree[edge[1]]:
                heapq.heappush(heap, edge)
    return total if added == n else None


def main() -> None:
    A, B, C, D, E, F, G = range(7)
    edges = [(A, B, 7), (A, D, 5), (B, C, 8), (B, D, 9), (B, E, 4), (C, E, 3),
             (D, E, 12), (D, F, 6), (E, F, 11), (E, G, 10), (F, G, 13), (C, G, 14)]
    assert all(prim(7, edges, s) == 35 for s in range(7))
    assert prim(4, [(0, 1, 1), (2, 3, 2)]) is None
    assert prim(4, [(0, 1, 1), (1, 2, 1), (2, 3, 1), (3, 0, 1)]) == 3
    assert prim(1, []) == 0
    print("prim ok")


main()
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class Prim {
    /** Lazy Prim. Returns the MST weight, or -1 if the graph is disconnected. */
    static long prim(int n, int[][] edges, int start) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(new int[]{e[2], e[1]});
            adj.get(e[1]).add(new int[]{e[2], e[0]});
        }
        boolean[] inTree = new boolean[n];
        inTree[start] = true;
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        heap.addAll(adj.get(start));
        long total = 0;
        int added = 1;
        while (!heap.isEmpty() && added < n) {
            int[] top = heap.poll();
            int w = top[0], v = top[1];
            if (inTree[v]) continue;                 // stale entry
            inTree[v] = true;
            total += w;
            added++;
            for (int[] e : adj.get(v)) if (!inTree[e[1]]) heap.add(e);
        }
        return added == n ? total : -1;
    }

    static void check(boolean cond, String msg) {
        if (!cond) throw new AssertionError(msg);
    }

    public static void main(String[] args) {
        final int A = 0, B = 1, C = 2, D = 3, E = 4, F = 5, G = 6;
        int[][] edges = {{A, B, 7}, {A, D, 5}, {B, C, 8}, {B, D, 9}, {B, E, 4}, {C, E, 3},
                         {D, E, 12}, {D, F, 6}, {E, F, 11}, {E, G, 10}, {F, G, 13}, {C, G, 14}};
        for (int s = 0; s < 7; s++) check(prim(7, edges, s) == 35, "start " + s);
        check(prim(4, new int[][]{{0, 1, 1}, {2, 3, 2}}, 0) == -1, "disconnected");
        check(prim(4, new int[][]{{0, 1, 1}, {1, 2, 1}, {2, 3, 1}, {3, 0, 1}}, 0) == 3, "square");
        check(prim(1, new int[0][], 0) == 0, "single vertex");
        System.out.println("prim ok");
    }
}
#include <cassert>
#include <cstdint>
#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

// Lazy Prim. Returns the MST weight, or -1 if the graph is disconnected.
std::int64_t prim(int n, const std::vector<std::vector<int>>& edges, int start) {
    std::vector<std::vector<std::pair<int, int>>> adj(n);   // (w, v)
    for (const auto& e : edges) {
        adj[e[0]].push_back({e[2], e[1]});
        adj[e[1]].push_back({e[2], e[0]});
    }
    std::vector<bool> in_tree(n, false);
    in_tree[start] = true;
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> heap(
        adj[start].begin(), adj[start].end());
    std::int64_t total = 0;
    int added = 1;
    while (!heap.empty() && added < n) {
        auto [w, v] = heap.top();
        heap.pop();
        if (in_tree[v]) continue;                    // stale entry
        in_tree[v] = true;
        total += w;
        ++added;
        for (const auto& e : adj[v]) if (!in_tree[e.second]) heap.push(e);
    }
    return added == n ? total : -1;
}

int main() {
    enum { A, B, C, D, E, F, G };
    std::vector<std::vector<int>> edges = {{A, B, 7}, {A, D, 5}, {B, C, 8}, {B, D, 9}, {B, E, 4}, {C, E, 3},
                                           {D, E, 12}, {D, F, 6}, {E, F, 11}, {E, G, 10}, {F, G, 13}, {C, G, 14}};
    for (int s = 0; s < 7; ++s) assert(prim(7, edges, s) == 35);
    assert(prim(4, {{0, 1, 1}, {2, 3, 2}}, 0) == -1);
    assert(prim(4, {{0, 1, 1}, {1, 2, 1}, {2, 3, 1}, {3, 0, 1}}, 0) == 3);
    assert(prim(1, {}, 0) == 0);
    std::cout << "prim ok\n";
}
type Item = [number, number]; // [weight, vertex]

class MinHeap {
  private a: Item[] = [];
  get size(): number {
    return this.a.length;
  }
  push(x: Item): void {
    const a = this.a;
    a.push(x);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (a[p][0] <= a[i][0]) break;
      [a[p], a[i]] = [a[i], a[p]];
      i = p;
    }
  }
  pop(): Item {
    const a = this.a;
    const top = a[0];
    const last = a.pop()!;
    if (a.length > 0) {
      a[0] = last;
      let i = 0;
      for (;;) {
        const l = 2 * i + 1, r = l + 1;
        let m = i;
        if (l < a.length && a[l][0] < a[m][0]) m = l;
        if (r < a.length && a[r][0] < a[m][0]) m = r;
        if (m === i) break;
        [a[m], a[i]] = [a[i], a[m]];
        i = m;
      }
    }
    return top;
  }
}

/** Lazy Prim. Returns the MST weight, or null if the graph is disconnected. */
function prim(n: number, edges: [number, number, number][], start = 0): number | null {
  const adj: Item[][] = Array.from({ length: n }, () => []);
  for (const [u, v, w] of edges) {
    adj[u].push([w, v]);
    adj[v].push([w, u]);
  }
  const inTree = new Array<boolean>(n).fill(false);
  inTree[start] = true;
  const heap = new MinHeap();
  for (const e of adj[start]) heap.push(e);
  let total = 0, added = 1;
  while (heap.size > 0 && added < n) {
    const [w, v] = heap.pop();
    if (inTree[v]) continue; // stale entry
    inTree[v] = true;
    total += w;
    added++;
    for (const e of adj[v]) if (!inTree[e[1]]) heap.push(e);
  }
  return added === n ? total : null;
}

function check(cond: boolean, msg: string): void {
  if (!cond) throw new Error(msg);
}

const [A, B, C, D, E, F, G] = [0, 1, 2, 3, 4, 5, 6];
const edges: [number, number, number][] = [[A, B, 7], [A, D, 5], [B, C, 8], [B, D, 9], [B, E, 4], [C, E, 3],
  [D, E, 12], [D, F, 6], [E, F, 11], [E, G, 10], [F, G, 13], [C, G, 14]];
for (let s = 0; s < 7; s++) check(prim(7, edges, s) === 35, `start ${s}`);
check(prim(4, [[0, 1, 1], [2, 3, 2]]) === null, "disconnected");
check(prim(4, [[0, 1, 1], [1, 2, 1], [2, 3, 1], [3, 0, 1]]) === 3, "square");
check(prim(1, []) === 0, "single vertex");
console.log("prim ok");

Variant: Prim for dense graphs and point sets

No adjacency list, no heap: compute weights on demand. This is the right tool when every pair of vertices is an edge — for example, connecting points where the cost is their distance.

def prim_dense(n: int, weight) -> int:
    """weight(u, v) -> cost. O(V^2) time, O(V) memory, works on complete graphs."""
    INF = float("inf")
    key = [INF] * n
    in_tree = [False] * n
    key[0] = 0
    total = 0
    for _ in range(n):
        u = min((v for v in range(n) if not in_tree[v]), key=key.__getitem__)
        in_tree[u] = True
        total += key[u]
        for v in range(n):
            if not in_tree[v]:
                w = weight(u, v)
                if w < key[v]:
                    key[v] = w                     # the decrease-key, for free
    return total


def main() -> None:
    pts = [(0, 0), (2, 2), (3, 10), (5, 2), (7, 0)]
    manhattan = lambda i, j: abs(pts[i][0] - pts[j][0]) + abs(pts[i][1] - pts[j][1])
    assert prim_dense(len(pts), manhattan) == 20

    INF = float("inf")
    A, B, C, D, E, F, G = range(7)
    M = [[INF] * 7 for _ in range(7)]
    for u, v, w in [(A, B, 7), (A, D, 5), (B, C, 8), (B, D, 9), (B, E, 4), (C, E, 3),
                    (D, E, 12), (D, F, 6), (E, F, 11), (E, G, 10), (F, G, 13), (C, G, 14)]:
        M[u][v] = M[v][u] = w
    assert prim_dense(7, lambda u, v: M[u][v]) == 35
    print("dense prim ok")


main()

Variant: Borůvka

def boruvka(n: int, edges: list[tuple[int, int, int]]) -> tuple[int, int]:
    """Returns (MST weight, number of rounds). Ties broken by edge index."""
    parent = list(range(n))

    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    components, total, rounds = n, 0, 0
    while components > 1:
        rounds += 1
        cheapest = [-1] * n                       # per root: index of lightest outgoing edge
        for i, (u, v, w) in enumerate(edges):
            ru, rv = find(u), find(v)
            if ru == rv:
                continue
            for r in (ru, rv):
                j = cheapest[r]
                if j == -1 or (w, i) < (edges[j][2], j):
                    cheapest[r] = i
        merged = False
        for r in range(n):
            i = cheapest[r]
            if i == -1:
                continue
            u, v, w = edges[i]
            ru, rv = find(u), find(v)
            if ru != rv:                          # may already be joined this round
                parent[ru] = rv
                total += w
                components -= 1
                merged = True
        if not merged:
            raise ValueError("graph is disconnected")
    return total, rounds


def kruskal_weight(n: int, edges: list[tuple[int, int, int]]) -> int:
    parent = list(range(n))

    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    total = 0
    for u, v, w in sorted(edges, key=lambda e: e[2]):
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            total += w
    return total


def main() -> None:
    A, B, C, D, E, F, G = range(7)
    edges = [(A, B, 7), (A, D, 5), (B, C, 8), (B, D, 9), (B, E, 4), (C, E, 3),
             (D, E, 12), (D, F, 6), (E, F, 11), (E, G, 10), (F, G, 13), (C, G, 14)]
    assert boruvka(7, edges) == (35, 2)

    import math
    import random
    rng = random.Random(3)
    for _ in range(300):
        n = rng.randint(2, 12)
        es = [(i, rng.randrange(i), rng.randint(1, 5)) for i in range(1, n)]   # spanning path keeps it connected
        es += [(rng.randrange(n), rng.randrange(n), rng.randint(1, 5)) for _ in range(rng.randint(0, 20))]
        es = [(u, v, w) for u, v, w in es if u != v]
        total, rounds = boruvka(n, es)            # many ties: the index tie-break matters
        assert total == kruskal_weight(n, es)
        assert rounds <= math.ceil(math.log2(n))
    print("boruvka ok")


main()

The random test uses weights from 1 to 5, so ties are everywhere. This sequential version has two guards against ties: the (w, i) tie-break, and the ru != rv re-check before each chosen edge is added. The re-check alone already prevents cycles here (an experiment with random tie-breaking and the re-check still matched Kruskal on all 300 graphs). The tie-break becomes essential in parallel or contraction-based implementations, which add every chosen edge of a round at once without re-checking.

Variant: maximum spanning tree and minimum bottleneck spanning tree

A maximum spanning tree is Kruskal with edges sorted in decreasing order (or an MST on negated weights); the cut and cycle properties hold with "heaviest" and "lightest" swapped. Use it for "most reliable network" (maximize the product of reliabilities = maximize the sum of logarithms) and for "widest path" queries.

A minimum bottleneck spanning tree (MBST) minimizes the largest edge rather than the sum. Every MST is an MBST (if an MST had a larger bottleneck edge than some tree , removing splits the MST into two sides, connects them with an edge lighter than , and swapping lowers the MST — contradiction). The converse is false: an MBST can have a larger total. In the example, replacing A–B (7) by B–D (9) gives a tree with total 37 but the same bottleneck 10. Camerini (1978) computes an MBST in by a median-splitting recursion, faster than any MST algorithm. The related minimum bottleneck path between and — the path whose heaviest edge is as light as possible — is simply the path between them in any MST.

def spanning_tree(n, edges, maximize=False):
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    tree = []
    for u, v, w in sorted(edges, key=lambda e: e[2], reverse=maximize):
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            tree.append((u, v, w))
    return tree


def bottleneck_on_path(tree, n, s, t):
    adj = [[] for _ in range(n)]
    for u, v, w in tree:
        adj[u].append((v, w))
        adj[v].append((u, w))
    best = {s: 0}
    stack = [s]
    while stack:                                   # DFS: the tree path is unique
        x = stack.pop()
        for y, w in adj[x]:
            if y not in best:
                best[y] = max(best[x], w)
                stack.append(y)
    return best[t]


A, B, C, D, E, F, G = range(7)
edges = [(A, B, 7), (A, D, 5), (B, C, 8), (B, D, 9), (B, E, 4), (C, E, 3),
         (D, E, 12), (D, F, 6), (E, F, 11), (E, G, 10), (F, G, 13), (C, G, 14)]
mst = spanning_tree(7, edges)
assert sum(w for *_, w in mst) == 35 and max(w for *_, w in mst) == 10
assert sum(w for *_, w in spanning_tree(7, edges, maximize=True)) == 66
other = [e for e in mst if e[2] != 7] + [(B, D, 9)]     # an MBST that is not an MST
assert sum(w for *_, w in other) == 37 and max(w for *_, w in other) == 10
assert bottleneck_on_path(mst, 7, A, G) == 10            # path A-B-E-G
assert bottleneck_on_path(mst, 7, D, C) == 7             # path D-A-B-E-C
print("max spanning tree / bottleneck ok")

Variant: second-best MST

The second-best MST is the cheapest spanning tree different from the MST (with distinct weights, the cheapest tree other than the unique MST). A classic exercise (CLRS problem 23-1) shows that some second-best tree differs from an MST by a single swap: add one non-tree edge and remove the heaviest tree edge on the tree path from to . So: compute the MST, precompute maxEdge[u][v] for all pairs by a DFS from every vertex (), and minimize over non-tree edges. With binary lifting on the tree (LCA & Binary Lifting) the path maximum costs per query, for total.

import itertools


def second_best_mst(n: int, edges: list[tuple[int, int, int]]) -> tuple[int, int]:
    """Returns (MST weight, second-best spanning tree weight). O(V^2 + E log E)."""
    parent = list(range(n))

    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    in_tree = [False] * len(edges)
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    best = 0
    for i in sorted(range(len(edges)), key=lambda i: edges[i][2]):
        u, v, w = edges[i]
        if find(u) != find(v):
            parent[find(u)] = find(v)
            in_tree[i] = True
            best += w
            adj[u].append((v, w))
            adj[v].append((u, w))
    max_edge = [[0] * n for _ in range(n)]
    for s in range(n):                             # max edge on the tree path s -> x
        seen = [False] * n
        seen[s] = True
        stack = [s]
        while stack:
            x = stack.pop()
            for y, w in adj[x]:
                if not seen[y]:
                    seen[y] = True
                    max_edge[s][y] = max(max_edge[s][x], w)
                    stack.append(y)
    second = min(best + w - max_edge[u][v] for i, (u, v, w) in enumerate(edges) if not in_tree[i])
    return best, second


def all_spanning_tree_weights(n, edges):
    out = []
    for comb in itertools.combinations(edges, n - 1):
        parent = list(range(n))

        def find(x):
            while parent[x] != x:
                x = parent[x]
            return x

        ok = True
        for u, v, _ in comb:
            ru, rv = find(u), find(v)
            if ru == rv:
                ok = False
                break
            parent[ru] = rv
        if ok:
            out.append(sum(w for *_, w in comb))
    return sorted(out)


A, B, C, D, E, F, G = range(7)
edges = [(A, B, 7), (A, D, 5), (B, C, 8), (B, D, 9), (B, E, 4), (C, E, 3),
         (D, E, 12), (D, F, 6), (E, F, 11), (E, G, 10), (F, G, 13), (C, G, 14)]
assert second_best_mst(7, edges) == (35, 37)           # add B-D 9, drop A-B 7
weights = all_spanning_tree_weights(7, edges)
assert len(weights) == 308 and weights[:2] == [35, 37]  # brute force agrees
print("second-best MST ok")

Variant: -clustering by cutting the heaviest MST edges

Single-linkage clustering into clusters: run Kruskal and stop when components remain — equivalently, delete the heaviest MST edges. Among all partitions into non-empty groups, this one maximizes the spacing, the minimum distance between points in different clusters (Kleinberg and Tardos, Algorithm Design, section 4.7, give the proof: any other partition splits some Kruskal component, and the edge Kruskal used inside that component is at most the spacing , so the other partition's spacing is at most ).

def k_clusters(n: int, edges: list[tuple[int, int, int]], k: int) -> tuple[list[set[int]], int]:
    parent = list(range(n))

    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    components = n
    order = sorted(edges, key=lambda e: e[2])
    i = 0
    while components > k:
        u, v, _ = order[i]
        i += 1
        if find(u) != find(v):
            parent[find(u)] = find(v)
            components -= 1
    spacing = min(w for u, v, w in order[i:] if find(u) != find(v))
    groups: dict[int, set[int]] = {}
    for x in range(n):
        groups.setdefault(find(x), set()).add(x)
    return sorted(groups.values(), key=min), spacing


A, B, C, D, E, F, G = range(7)
edges = [(A, B, 7), (A, D, 5), (B, C, 8), (B, D, 9), (B, E, 4), (C, E, 3),
         (D, E, 12), (D, F, 6), (E, F, 11), (E, G, 10), (F, G, 13), (C, G, 14)]
groups, spacing = k_clusters(7, edges, 3)
assert groups == [{A, D, F}, {B, C, E}, {G}] and spacing == 7   # cut E-G (10) and A-B (7)
print("k-clustering ok")

Variant: 2-approximation for metric TSP

For points where distances obey the triangle inequality, the double-tree algorithm builds the MST, walks it in DFS preorder, and visits vertices in that order. The tour costs at most twice the optimum:

  1. Deleting any edge from an optimal tour leaves a spanning path, which is a spanning tree, so .
  2. A full walk around the MST (down and back up every edge) costs exactly .
  3. Skipping already-visited vertices replaces a sub-walk by a direct edge, which by the triangle inequality is no longer. So the preorder tour costs at most .

Christofides (1976) improves the factor to by adding a minimum-weight perfect matching on the MST's odd-degree vertices; Karlin, Klein and Oveis Gharan (2021) shaved it to slightly below . Without the triangle inequality, no constant-factor approximation exists unless P = NP.

import itertools
import math
import random


def tsp_double_tree(pts: list[tuple[float, float]]) -> float:
    n = len(pts)
    dist = lambda i, j: math.dist(pts[i], pts[j])
    key, parent, in_tree = [math.inf] * n, [-1] * n, [False] * n
    key[0] = 0.0
    children: list[list[int]] = [[] for _ in range(n)]
    for _ in range(n):                                   # O(V^2) Prim
        u = min((v for v in range(n) if not in_tree[v]), key=key.__getitem__)
        in_tree[u] = True
        if parent[u] >= 0:
            children[parent[u]].append(u)
        for v in range(n):
            if not in_tree[v] and dist(u, v) < key[v]:
                key[v], parent[v] = dist(u, v), u
    order, stack = [], [0]
    while stack:                                         # preorder walk
        x = stack.pop()
        order.append(x)
        stack.extend(reversed(children[x]))
    return sum(dist(order[i], order[(i + 1) % n]) for i in range(n))


def tsp_exact(pts: list[tuple[float, float]]) -> float:
    n = len(pts)
    return min(sum(math.dist(pts[t[i]], pts[t[(i + 1) % n]]) for i in range(n))
               for t in ((0,) + p for p in itertools.permutations(range(1, n))))


rng = random.Random(11)
worst = 0.0
for _ in range(30):
    pts = [(rng.random(), rng.random()) for _ in range(8)]
    ratio = tsp_double_tree(pts) / tsp_exact(pts)
    assert 1.0 - 1e-9 <= ratio <= 2.0
    worst = max(worst, ratio)
print(f"double-tree / optimal, worst of 30 random instances: {worst:.3f}")

On random points the ratio is typically far below 2; the bound is about worst cases.

Variant: graph-based image segmentation (Felzenszwalb–Huttenlocher)

Felzenszwalb and Huttenlocher (2004) segment an image by running Kruskal on the pixel grid — edges between neighbouring pixels weighted by colour difference — but merging two components only if the edge is no heavier than each component's internal variation plus a size-dependent slack: merge via edge iff , where is the largest MST edge inside . Because edges are processed in sorted order, of a merged component is just the current edge weight. It runs in and is still a standard baseline (and the region-proposal step of early object detectors such as Selective Search). A one-dimensional version:

def segment(signal: list[int], k: float) -> list[int]:
    n = len(signal)
    parent, size, internal = list(range(n)), [1] * n, [0.0] * n

    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    edges = sorted((abs(signal[i] - signal[i + 1]), i, i + 1) for i in range(n - 1))
    for w, u, v in edges:
        a, b = find(u), find(v)
        if a != b and w <= min(internal[a] + k / size[a], internal[b] + k / size[b]):
            if size[a] < size[b]:
                a, b = b, a
            parent[b] = a
            size[a] += size[b]
            internal[a] = w                       # sorted order: w is the new max MST edge
    roots, labels = {}, []
    for i in range(n):
        labels.append(roots.setdefault(find(i), len(roots)))
    return labels


assert segment([10, 11, 12, 50, 51, 52, 90], k=5) == [0, 0, 0, 1, 1, 1, 2]
assert segment([10, 11, 12, 50, 51, 52, 90], k=500) == [0] * 7   # large k: coarser segments
print("segmentation ok")

Real-world uses

  • Network design. The original application, and still the textbook one: laying cable, pipe or fibre to connect sites at minimum cost when any spanning connection is acceptable. Real designs add redundancy (2-edge-connected networks), capacity and distance constraints, which turn the problem into harder variants; the MST is the starting point and a lower bound. See The Network Layer.
  • A common confusion: Ethernet's Spanning Tree Protocol. STP (IEEE 802.1D) breaks loops in switched LANs by building a spanning tree, but it is not an MST: each switch keeps its least-cost path to an elected root bridge, so the result is a shortest-path tree from the root. See The Data Link Layer.
  • Clustering. Single-linkage hierarchical clustering is exactly Kruskal; the dendrogram is the order of merges, and cutting it at a height is cutting MST edges above that weight. SciPy's scipy.cluster.hierarchy.linkage(method="single") computes it, and HDBSCAN builds an MST on a "mutual reachability" distance and condenses it. Zahn (1971) introduced MST-based clustering by removing "inconsistent" long edges. See Clustering.
  • Approximation algorithms. The MST is the backbone of the 2-approximation for metric TSP and of Christofides' 1.5-approximation; the MST over terminals' shortest-path distances is a 2-approximation for the Steiner tree problem. Vehicle routing and PCB drilling heuristics start from these.
  • Image segmentation and computer vision. Felzenszwalb–Huttenlocher segmentation (above) and its descendants; MST-based stereo matching and cost aggregation (Yang, "A Non-Local Cost Aggregation Method for Stereo Matching", CVPR 2012) filter along the MST of the image grid.
  • Phylogenetics and bioinformatics. Minimum spanning networks summarize relationships between haplotypes; MST-based methods group sequences when a full tree reconstruction is too expensive.
  • Maze generation and procedural content. Randomized Kruskal and Prim generate perfect mazes; games use MSTs over room centres (often on a Delaunay triangulation) to guarantee dungeons are connected, then add a few extra edges for loops.
  • Circuit design. Rectilinear (Manhattan) MSTs estimate wire length for nets during VLSI placement, and are the starting point for rectilinear Steiner tree heuristics that route the actual wires.
  • Data summarization and visualization. Plotting the MST of a correlation matrix ("MST of stock returns", Mantegna 1999) is a standard way to visualize the structure of financial markets and other high-dimensional data.

Pitfalls & edge cases

  • Disconnected graphs. Kruskal silently returns a forest with fewer than edges; Prim silently returns the tree of the start vertex's component. Check the edge count (or vertex count) and report "impossible" explicitly.
  • Directed graphs. MST is defined for undirected graphs. Running Prim on a directed adjacency list gives nonsense; the directed problem (minimum arborescence) needs Chu–Liu/Edmonds, or with Gabow et al.'s improvement.
  • Negative weights are fine. Unlike Dijkstra, all three MST algorithms handle negative edge weights: only the relative order of weights matters. Adding a constant to every weight does not change the MST (every spanning tree has exactly edges).
  • Parallel edges and self-loops. Self-loops are never in a spanning tree; Kruskal rejects them automatically (find(u) == find(u)), but a hand-written Prim may not. Parallel edges are harmless — only the lightest can be in an MST.
  • Ties. Many MSTs may exist; any algorithm returns one. Do not write tests that compare edge sets when weights repeat — compare total weight. Borůvka needs a consistent tie-break.
  • Overflow. edges of weight up to need 64-bit totals; in Java and C++ accumulate in long / int64_t.
  • Prim heap entries. In lazy Prim, check in_tree[v] when popping, not only when pushing — the same vertex can be pushed many times. Forgetting this adds a vertex twice and overcounts.
  • Sorting comparator bugs. (a, b) -> a[2] - b[2] overflows in Java for weights near ; use Integer.compare.
  • Dense input with Kruskal. For points, the complete graph has edges; materializing and sorting them costs gigabytes. Use Prim, or a geometric MST.
  • Confusing MST with shortest paths. The path between two vertices in the MST is generally not their shortest path. In the example, the MST path from D to E is D–A–B–E with length , but the direct edge D–E has length 12.

Variations

  • Minimum spanning forest: Kruskal or Borůvka on a disconnected graph; one tree per component.
  • Maximum spanning tree: reverse the sort. Equivalent to MST on negated weights.
  • Minimum bottleneck spanning tree / path: every MST is one; Camerini's algorithm computes an MBST directly. Bottleneck path queries in bulk: Kruskal reconstruction tree, or LCA with path maxima over the MST.
  • Second-best MST, MST sensitivity, "edges in some/every MST": single-swap structure; process equal-weight groups together in Kruskal to classify edges (practice problems 9–12 below).
  • Euclidean MST: the MST of points in the plane under Euclidean distance is a subgraph of the Delaunay triangulation (Shamos and Hoey, 1975), which has at most edges and is computable in ; Kruskal on those edges gives the EMST in . See Spatial Trees for the k-d trees used in higher dimensions.
  • Manhattan (rectilinear) MST: for each point, only the nearest neighbour in each of the 8 octants around it can be an MST neighbour; by symmetry four sweeps with a Fenwick tree find candidate edges, and Kruskal on them gives .
  • Steiner tree — connect a given set of terminals, possibly through other vertices — is NP-hard (it is one of Karp's 21 NP-complete problems from 1972, in its decision form), and the Euclidean version is NP-hard too. The contrast with MST is the point: allowing optional junction vertices destroys the matroid structure. The MST of the metric closure on the terminals is a 2-approximation.
  • Degree-constrained MST (every vertex degree at most ) is NP-hard for — that is the Hamiltonian path problem.
  • Dynamic MST: maintain the MST under edge insertions and deletions; Holm, de Lichtenberg and Thorup (2001) do it in polylogarithmic amortized time. Insert-only is easy: the new edge replaces the heaviest edge on its tree path if lighter.
  • Minimum arborescence (directed MST): Chu–Liu/Edmonds; contract cycles of cheapest incoming edges.
  • MST verification: given a tree, check whether it is an MST in (Komlós 1985; King 1997) — a building block of the linear-time randomized algorithm.

Practice ladder

Problems are described in my own words; follow the links for the official statements.

1. Min Cost to Connect All Points (LeetCode 1584) — Points in the plane, cost = Manhattan distance, connect all at minimum cost. Teaches the dense-graph choice: Prim beats building edges.

Hint

, so the complete graph has about 500,000 edges. Kruskal works but sorts them all; array Prim computes distances on the fly with memory.

Solution
def min_cost_connect_points(points: list[list[int]]) -> int:
    n = len(points)
    INF = float("inf")
    key, in_tree = [INF] * n, [False] * n
    key[0], total = 0, 0
    for _ in range(n):
        u = min((v for v in range(n) if not in_tree[v]), key=key.__getitem__)
        in_tree[u] = True
        total += key[u]
        ux, uy = points[u]
        for v in range(n):
            if not in_tree[v]:
                d = abs(ux - points[v][0]) + abs(uy - points[v][1])
                if d < key[v]:
                    key[v] = d
    return total


assert min_cost_connect_points([[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]]) == 20
assert min_cost_connect_points([[3, 12], [-2, 5], [-4, 1]]) == 18
assert min_cost_connect_points([[0, 0]]) == 0
print("connect all points ok")

time, space.

2. Connecting Cities With Minimum Cost (LeetCode 1135) — A plain MST on an edge list; return if impossible. Teaches disconnected-graph handling.

Hint

Kruskal; at the end, if fewer than edges were accepted, return .

3. Road Reparation (CSES 1675) — MST at vertices and edges, report "IMPOSSIBLE" if disconnected. Teaches 64-bit totals and fast I/O.

Hint

Weights up to times edges overflow 32 bits. In Python read all input with sys.stdin.buffer.read().split().

4. Optimize Water Distribution in a Village (LeetCode 1168) — Each house can dig its own well at a cost or be piped to a neighbour. Teaches the virtual node trick: a well is an edge to a "water source" vertex 0.

Hint

Add vertex 0 and an edge of weight wells[i-1] for every house. The answer is the MST of the augmented graph.

Solution
def min_cost_to_supply_water(n: int, wells: list[int], pipes: list[list[int]]) -> int:
    edges = [(w, 0, i + 1) for i, w in enumerate(wells)] + [(w, u, v) for u, v, w in pipes]
    parent = list(range(n + 1))

    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    total = 0
    for w, u, v in sorted(edges):
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            total += w
    return total


assert min_cost_to_supply_water(3, [1, 2, 2], [[1, 2, 1], [2, 3, 1]]) == 3
assert min_cost_to_supply_water(2, [1, 1], [[1, 2, 1], [1, 2, 2]]) == 2
print("water distribution ok")

for pipes.

5. Path With Minimum Effort (LeetCode 1631) — A height grid; minimize the largest height step on a path from corner to corner. Teaches the minimum bottleneck path via Kruskal: add edges in increasing order until the corners connect.

Hint

Edges between neighbouring cells weigh abs(h1 - h2). Sort them; union until find(0) == find(rows*cols - 1); the last weight added is the answer. (Dijkstra with max instead of + also works.)

6. Make It Connected (Codeforces 1095F) — Joining any two vertices costs the sum of their values, plus some special offers. Teaches pruning a complete graph: only edges to the minimum-value vertex matter among the non-offer edges.

Hint

For non-offer edges, , so connecting everything to the vertex with the smallest value dominates. Kruskal on those edges plus the offers.

7. Shichikuji and Power Grid (Codeforces 1245D) — Cities can build a power station or connect to another city by wire (cost depends on Manhattan distance). Teaches virtual node + dense Prim, and reconstructing which choice each city made.

Hint

Virtual vertex 0 with edge cost to each city; wire costs . : Prim, recording parent[v] to print the stations (parent 0) and the wires.

8. Built? (AtCoder ABC 065 D) — Connect towns where the cost between two towns is . Teaches reducing candidate edges by sorting: only neighbours in x-order and in y-order can matter.

Hint

Sort towns by x and add an edge between consecutive towns with weight ; same for y. That gives candidate edges, and the MST over them equals the full MST.

9. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree (LeetCode 1489) — Classify each edge as in every MST, in some MST, or neither. Teaches the cut/cycle properties operationally.

Hint

Let be the MST weight. Edge is critical if the MST without is heavier (or impossible); otherwise it is pseudo-critical if the MST forced to include still weighs . , so is fine.

Solution
def critical_edges(n: int, edges: list[list[int]]) -> list[list[int]]:
    order = sorted(range(len(edges)), key=lambda i: edges[i][2])

    def mst(skip: int = -1, force: int = -1) -> float:
        parent = list(range(n))

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        total, used = 0, 0
        if force >= 0:
            u, v, w = edges[force]
            parent[find(u)] = find(v)
            total, used = w, 1
        for i in order:
            if i == skip:
                continue
            u, v, w = edges[i]
            ru, rv = find(u), find(v)
            if ru != rv:
                parent[ru] = rv
                total += w
                used += 1
        return total if used == n - 1 else float("inf")

    base = mst()
    critical, pseudo = [], []
    for i in range(len(edges)):
        if mst(skip=i) > base:
            critical.append(i)
        elif mst(force=i) == base:
            pseudo.append(i)
    return [critical, pseudo]


assert critical_edges(5, [[0, 1, 1], [1, 2, 1], [2, 3, 2], [0, 3, 2], [0, 4, 3], [3, 4, 3], [1, 4, 6]]) == [[0, 1], [2, 3, 4, 5]]
assert critical_edges(4, [[0, 1, 1], [1, 2, 1], [2, 3, 1], [0, 3, 1]]) == [[], [0, 1, 2, 3]]
print("critical edges ok")

after one sort.

10. Edges in MST (Codeforces 160D) — The same classification at scale. Teaches the efficient method: process equal-weight groups together and find bridges in the contracted graph of each group.

Hint

For each weight group, edges whose endpoints are already connected are "none". Among the rest, contract DSU components to vertices; an edge is in every MST iff it is a bridge of this small multigraph (see Connectivity for bridges). Then union the whole group.

11. MST Unification (Codeforces 1108F) — Increase some edge weights by 1, as few as possible, so the MST becomes unique without changing its weight. Teaches counting "interchangeable" edges inside an equal-weight group.

Hint

Within each weight group, count edges that connect different components before the group is processed, then subtract the number actually used when processing the group. The difference is the number of edges that must be bumped.

12. Minimum spanning tree for each edge (Codeforces 609E) — For every edge, the weight of the cheapest spanning tree that contains it. Teaches the single-swap structure plus path-maximum queries with binary lifting.

Hint

Answer for edge is , where the max is over MST edges on the tree path. Binary lifting stores the max edge to each -th ancestor.

13. Xor-MST (Codeforces 888G) — The complete graph on numbers with edge weight = XOR of the endpoints. Teaches Borůvka (or divide and conquer) on a binary trie, never materializing edges.

Hint

Build a binary trie of the values. At each trie node with two children, the subtrees must be joined by exactly one edge, the minimum XOR pair between them; recurse. This is Borůvka's "cheapest edge between components" computed by the trie.

14. Manhattan MST (Library Checker) — The MST of points under Manhattan distance. Teaches the octant candidate-edge reduction from the Variations section.

Hint

For each of four coordinate transformations, sort points and sweep with a Fenwick tree (or sorted structure) that returns, for each point, the nearest point in one octant. Collect at most candidate edges and run Kruskal.

Common mistakes & interview follow-ups

"Kruskal or Prim?" Kruskal for sparse graphs given as edge lists, for offline threshold sweeps, and when you also want a DSU afterwards. Prim (heap) when you have an adjacency list; Prim (array) for dense graphs and point sets. Asymptotically both are with binary heaps.

"Prove it works." State the cut property, prove it by the exchange argument (add the light edge, a cycle forms, it crosses the cut twice, swap out the other crossing edge), then say each algorithm only ever adds a light edge of a cut that respects the edges chosen so far.

"What if weights are negative?" No change. Only the order of weights matters. (Contrast with Dijkstra.)

"What if all weights are equal?" Any spanning tree is an MST; BFS or DFS gives one in .

"What if weights are small integers?" Counting sort the edges and Kruskal is . With weights in , BFS-like tricks give .

"What if an edge's weight decreases / a new edge arrives?" Add it to the tree; it forms one cycle; remove the heaviest edge on that cycle. with a tree walk, with link-cut trees. Weight increase of a tree edge: remove it, and reconnect the two sides with the lightest crossing edge.

"Is the MST path the shortest path?" No; it minimizes the maximum edge on the path, not the sum.

"Does the MST stay the same if I square all weights / add 10 to all weights?" Yes for any strictly increasing transformation (the order is preserved), and yes for adding a constant. Shortest paths do not survive adding a constant to every edge.

"How would you do this on a graph with edges?" Borůvka rounds in a distributed framework (each round is a map-reduce: per-component minimum, then contraction), or filter-Kruskal style sampling: build an MST of a random sample, discard edges heavier than the max on their sample-tree path, repeat on the survivors.

Common mistakes interviewers watch for: Prim without stale-entry check; Kruskal without a disconnected check; DSU without path compression or union by size on large inputs; comparing edge sets in tests with tied weights; claiming the MST path is a shortest path.

Quick quiz

1. In the example graph, which single edge, if its weight rose from 7 to 12, would change the MST, and what would the new weight be?

Answer

A–B. With A–B at 12, the cut between and has crossing edges B–D 9, E–F 11, D–E 12, A–B 12, F–G 13; the light edge becomes B–D (9). New MST weight .

2. Why can Kruskal stop after accepted edges, and why does it not improve the worst-case complexity?

Answer

A spanning tree has exactly edges, so after that every remaining edge would close a cycle. The sort already cost , so stopping early only saves DSU work.

3. A graph has distinct weights. Is its maximum-weight edge ever in the MST?

Answer

Yes, if it is a bridge (the only edge across some cut): then it is the lightest crossing edge of that cut and must be in every spanning tree. Otherwise it lies on a cycle where it is the heaviest edge, and the cycle property excludes it.

4. Borůvka on a graph with 1000 vertices: what is the maximum number of rounds?

Answer

. Each round at least halves the number of components: 1000 → 500 → … → 1 within 10 rounds.

5. Your MST has total weight 35. Is the shortest path from D to E at most the MST path length?

Answer

The question is a trap: the shortest path can be shorter than the MST path. In the example the MST path D–A–B–E has length 16, but the edge D–E alone is 12. MSTs minimize the total tree weight and the bottleneck, not individual path lengths.

Further reading / sources

  • Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 3rd ed., chapter 23 "Minimum Spanning Trees" (generic MST, safe edges, Kruskal, Prim; problem 23-1 on second-best MSTs, problem 23-4 on alternative algorithms). The 4th edition covers it in chapter 21.
  • Jon Kleinberg and Éva Tardos, Algorithm Design, sections 4.5 (MST, cut and cycle properties) and 4.7 (clustering).
  • Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed., section 4.3 (lazy and eager Prim, Kruskal).
  • R. L. Graham and Pavol Hell, "On the History of the Minimum Spanning Tree Problem", Annals of the History of Computing 7(1), 1985 — Borůvka, Jarník, Kruskal, Prim and the rest.
  • Joseph B. Kruskal, "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem", Proceedings of the AMS 7(1), 1956; R. C. Prim, "Shortest Connection Networks and Some Generalizations", Bell System Technical Journal 36(6), 1957.
  • David R. Karger, Philip N. Klein, Robert E. Tarjan, "A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees", JACM 42(2), 1995; Bernard Chazelle, "A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity", JACM 47(6), 2000; Seth Pettie and Vijaya Ramachandran, "An Optimal Minimum Spanning Tree Algorithm", JACM 49(1), 2002.
  • Pedro F. Felzenszwalb and Daniel P. Huttenlocher, "Efficient Graph-Based Image Segmentation", International Journal of Computer Vision 59(2), 2004.
  • Nicos Christofides, "Worst-case analysis of a new heuristic for the travelling salesman problem", Report 388, Carnegie Mellon University, 1976.
  • cp-algorithms: Minimum spanning tree – Prim's algorithm, Kruskal's algorithm with DSU, Second best MST, and the Manhattan MST article.

Previous lesson: Union-Find in Depth · Next lesson: Connectivity: Bridges, Articulation Points, SCCs & Condensation

Related: Module 4 overview: Graphs · Greedy Algorithms · Heaps & Priority Queues · Shortest Paths · LCA & Binary Lifting · Spatial Trees · Advanced Data Structures · Clustering · Course home