Minimum spanning trees

intermediateCommon atGoogleAmazonMetaRead firstUnion-findHeapsGreedy algorithmsPractise in the Sandbox →

A minimum spanning tree (MST) is a set of V − 1 edges that connects every node of a connected, undirected, weighted graph with the smallest total weight. The cut property says the cheapest edge crossing any split of the nodes is safe to take. Kruskal applies it by scanning edges cheapest-first and skipping any that would close a cycle (union-find), O(E log E). Prim grows one tree, always adding the cheapest edge that leaves it (min-heap), O(E log V).

The idea in plain words

You need to lay cable between 6 buildings. Each possible link has a cost. Every building must be reachable from every other, possibly through others, and you want to spend as little as possible.

Two observations:

• The answer never contains a cycle. If it did, you could drop the most expensive cable on the cycle and everything would still be connected. So the answer is a tree: exactly V − 1 edges.
• Cut property. Split the buildings into any two groups. Some cable must cross between them. The cheapest crossing cable is always part of some optimal answer. (Swap it in for whatever crossing edge an optimal tree uses; the total can’t go up.)

Both classic algorithms just choose cuts cleverly:

• Kruskal considers edges from cheapest to most expensive. An edge between two different components is the cheapest edge across the cut “this component vs the rest”, so take it. An edge inside one component would close a cycle, so skip it.
• Prim keeps one growing tree. The cut is “tree vs everything else”, and it takes the cheapest edge across.

See it

Edit the edges and step through. In Kruskal mode, watch the sorted list and the union-find parent row: an edge is rejected exactly when both ends already share a root. Switch to Prim and compare: different order, same total.

Cheapest safe edge, until everything is connected

edit the graph, then step

undirected edges: a-b 4

DefaultTiesDisconnected

edges sorted by weight

b-c 1a-c 2d-e 2e-f 3a-b 4b-d 5d-f 6c-d 8c-e 10

abcdefparentabcdef

tree edges0/5

total weight0

edge just takenin the treerejected: would close a cyclealready connected

Kruskal: sort all edges by weight, then scan cheapest first. Union-find tracks which nodes are already connected; every node starts as its own component.

↺◀▶ Play▶1 / 8

Try Ties: several edges have the same weight, so there are several MSTs, and the two algorithms may pick different edges. Then try Disconnected: there’s no spanning tree, and each algorithm fails in its own way.

When to reach for it

The problem says…	Why an MST fits
“connect all points / cities / computers at minimum total cost”	That’s the definition.
“minimum cost to make the network connected” with candidate links	MST over the candidate links (plus already-free links at weight 0).
“points on a plane, cost = distance between them”	MST over the complete graph; use dense Prim, O(V²).
“minimise the largest edge on the path between two nodes”	The MST path between them is a minimax (bottleneck) path.
“group items into k clusters as far apart as possible”	Run Kruskal and stop with k components left (single-linkage clustering).

MST is not shortest paths

An MST minimises the total weight of the network. It does not give the cheapest route between two specific nodes; that’s Dijkstra. Prim’s code looks almost identical to Dijkstra’s, but its heap key is the single edge weight w(u, v), not the path cost dist[u] + w(u, v).

How it works

Kruskal

1. Sort the edges by weight.
2. For each edge (u, v): if find(u) == find(v), the ends are already connected; skip it.
3. Otherwise union(u, v) and add the edge to the tree.
4. Stop after V − 1 edges. Fewer at the end means the graph is disconnected (you got a spanning forest).

Python

kruskal.py

def kruskal(n: int, edges: list[tuple[int, int, int]]) -> tuple[int, list[tuple[int, int, int]]]:
    """Minimum spanning tree (forest if disconnected) of nodes 0..n-1. Edges are (u, v, w)."""
    parent = list(range(n))
    size = [1] * n

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

    total, tree = 0, []
    for u, v, w in sorted(edges, key=lambda e: e[2]):   # 1. cheapest edges first
        ru, rv = find(u), find(v)
        if ru == rv:                        # 2. same component: edge would close a cycle
            continue
        if size[ru] < size[rv]:             # 3. union by size, then take the edge
            ru, rv = rv, ru
        parent[rv] = ru
        size[ru] += size[rv]
        total += w
        tree.append((u, v, w))
        if len(tree) == n - 1:              # 4. spanning tree complete: stop early
            break
    return total, tree


if __name__ == "__main__":
    edges = [(0, 1, 4), (0, 2, 2), (1, 2, 1), (1, 3, 5), (2, 3, 8), (2, 4, 10), (3, 4, 2), (3, 5, 6), (4, 5, 3)]
    total, tree = kruskal(6, edges)
    assert total == 13 and len(tree) == 5
    assert kruskal(4, [(0, 1, 1), (2, 3, 1)]) == (2, [(0, 1, 1), (2, 3, 1)])  # forest
    print("ok")

TypeScript

kruskal.ts

import assert from "node:assert/strict";

type Edge = [u: number, v: number, w: number];

/** Minimum spanning tree (forest if disconnected) of nodes 0..n-1. */
export function kruskal(n: number, edges: Edge[]): { total: number; tree: Edge[] } {
  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 keeps trees flat
      x = parent[x];
    }
    return x;
  };
  let total = 0;
  const tree: Edge[] = [];
  for (const [u, v, w] of [...edges].sort((a, b) => a[2] - b[2])) { // 1. cheapest edges first
    let ru = find(u), rv = find(v);
    if (ru === rv) continue; // 2. same component: edge would close a cycle
    if (size[ru] < size[rv]) [ru, rv] = [rv, ru]; // 3. union by size, then take the edge
    parent[rv] = ru;
    size[ru] += size[rv];
    total += w;
    tree.push([u, v, w]);
    if (tree.length === n - 1) break; // 4. spanning tree complete: stop early
  }
  return { total, tree };
}

const edges: Edge[] = [[0, 1, 4], [0, 2, 2], [1, 2, 1], [1, 3, 5], [2, 3, 8], [2, 4, 10], [3, 4, 2], [3, 5, 6], [4, 5, 3]];
const { total, tree } = kruskal(6, edges);
assert.equal(total, 13);
assert.equal(tree.length, 5);
assert.deepEqual(kruskal(4, [[0, 1, 1], [2, 3, 1]]), { total: 2, tree: [[0, 1, 1], [2, 3, 1]] }); // forest
console.log("ok");

C#

kruskal.cs

(int, int, int)[] edges = [(0, 1, 4), (0, 2, 2), (1, 2, 1), (1, 3, 5), (2, 3, 8), (2, 4, 10), (3, 4, 2), (3, 5, 6), (4, 5, 3)];
var (total, tree) = Kruskal(6, edges);
if (total != 13 || tree.Count != 5) throw new Exception($"got {total}");
if (Kruskal(4, [(0, 1, 1), (2, 3, 1)]).Total != 2) throw new Exception("forest");
Console.WriteLine("ok");

// Minimum spanning tree (forest if disconnected) of nodes 0..n-1. Edges are (u, v, w).
static (int Total, List<(int, int, int)> Tree) Kruskal(int n, (int U, int V, int W)[] edges)
{
    var parent = Enumerable.Range(0, n).ToArray();
    var size = Enumerable.Repeat(1, n).ToArray();
    int Find(int x)
    {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } // path halving
        return x;
    }
    int total = 0;
    var tree = new List<(int, int, int)>();
    foreach (var (u, v, w) in edges.OrderBy(e => e.W))   // 1. cheapest edges first
    {
        int ru = Find(u), rv = Find(v);
        if (ru == rv) continue;                           // 2. same component: would close a cycle
        if (size[ru] < size[rv]) (ru, rv) = (rv, ru);     // 3. union by size, then take the edge
        parent[rv] = ru;
        size[ru] += size[rv];
        total += w;
        tree.Add((u, v, w));
        if (tree.Count == n - 1) break;                   // 4. spanning tree complete
    }
    return (total, tree);
}

Prim

The heap version mirrors Dijkstra: push (w, v) for every edge leaving the tree, pop the cheapest, skip it if v is already in the tree. For a dense graph (or points in the plane, where every pair is an edge) the simpler array version is faster: keep best[v], the cheapest known edge from the tree to v, and scan for the minimum each step.

1. Start with node 0: best[0] = 0, everything else ∞.
2. Pick the node outside the tree with the smallest best.
3. Add it to the tree and add best[u] to the total.
4. For each outside node v, lower best[v] to w(u, v) if that’s cheaper.

Python

prim_dense.py

import math


def prim_dense(w: list[list[float]]) -> float:
    """MST weight from an adjacency matrix (math.inf = no edge). O(V^2), best for dense graphs."""
    n = len(w)
    in_tree = [False] * n
    best = [math.inf] * n               # cheapest known edge from the tree to each node
    best[0] = 0                         # 1. start the tree at node 0
    total = 0.0
    for _ in range(n):
        u = min((v for v in range(n) if not in_tree[v]), key=lambda v: best[v])  # 2. closest outside node
        if best[u] == math.inf:
            raise ValueError("graph is disconnected")
        in_tree[u] = True               # 3. add it with its cheapest connecting edge
        total += best[u]
        for v in range(n):              # 4. its edges may now be the cheapest way to reach others
            if not in_tree[v] and w[u][v] < best[v]:
                best[v] = w[u][v]
    return total


if __name__ == "__main__":
    INF = math.inf
    w = [[INF] * 6 for _ in range(6)]
    for a, b, c in [(0, 1, 4), (0, 2, 2), (1, 2, 1), (1, 3, 5), (2, 3, 8), (2, 4, 10), (3, 4, 2), (3, 5, 6), (4, 5, 3)]:
        w[a][b] = w[b][a] = c
    assert prim_dense(w) == 13
    print("ok")

TypeScript

prim_dense.ts

import assert from "node:assert/strict";

/** MST weight from an adjacency matrix (Infinity = no edge). O(V^2), best for dense graphs. */
export function primDense(w: number[][]): number {
  const n = w.length;
  const inTree = new Array<boolean>(n).fill(false);
  const best = new Array<number>(n).fill(Infinity); // cheapest known edge from the tree to each node
  best[0] = 0; // 1. start the tree at node 0
  let total = 0;
  for (let step = 0; step < n; step++) {
    let u = -1; // 2. closest node still outside the tree
    for (let v = 0; v < n; v++) if (!inTree[v] && (u === -1 || best[v] < best[u])) u = v;
    if (best[u] === Infinity) throw new Error("graph is disconnected");
    inTree[u] = true; // 3. add it with its cheapest connecting edge
    total += best[u];
    for (let v = 0; v < n; v++) { // 4. its edges may now be the cheapest way to reach others
      if (!inTree[v] && w[u][v] < best[v]) best[v] = w[u][v];
    }
  }
  return total;
}

const w = Array.from({ length: 6 }, () => new Array<number>(6).fill(Infinity));
for (const [a, b, c] of [[0, 1, 4], [0, 2, 2], [1, 2, 1], [1, 3, 5], [2, 3, 8], [2, 4, 10], [3, 4, 2], [3, 5, 6], [4, 5, 3]]) {
  w[a][b] = w[b][a] = c;
}
assert.equal(primDense(w), 13);
console.log("ok");

C#

prim_dense.cs

const double Inf = double.PositiveInfinity;
var w = new double[6, 6];
for (int i = 0; i < 6; i++) for (int j = 0; j < 6; j++) w[i, j] = Inf;
foreach (var (a, b, c) in new[] { (0, 1, 4), (0, 2, 2), (1, 2, 1), (1, 3, 5), (2, 3, 8), (2, 4, 10), (3, 4, 2), (3, 5, 6), (4, 5, 3) })
    w[a, b] = w[b, a] = c;
if (PrimDense(w) != 13) throw new Exception("expected 13");
Console.WriteLine("ok");

// MST weight from an adjacency matrix (infinity = no edge). O(V^2), best for dense graphs.
static double PrimDense(double[,] w)
{
    int n = w.GetLength(0);
    var inTree = new bool[n];
    var best = Enumerable.Repeat(double.PositiveInfinity, n).ToArray(); // cheapest edge from the tree
    best[0] = 0;                                              // 1. start the tree at node 0
    double total = 0;
    for (int step = 0; step < n; step++)
    {
        int u = -1;                                           // 2. closest node still outside
        for (int v = 0; v < n; v++) if (!inTree[v] && (u == -1 || best[v] < best[u])) u = v;
        if (double.IsInfinity(best[u])) throw new InvalidOperationException("graph is disconnected");
        inTree[u] = true;                                     // 3. add it with its cheapest edge
        total += best[u];
        for (int v = 0; v < n; v++)                           // 4. its edges may be cheaper for others
            if (!inTree[v] && w[u, v] < best[v]) best[v] = w[u, v];
    }
    return total;
}

What it costs

Algorithm	Time	Space	Best for
Kruskal	O(E log E) for the sort, plus nearly O(E) for union-find	O(V + E)	sparse graphs, edge lists, already-sorted edges
Prim, binary heap	O(E log V)	O(V + E)	sparse graphs given as adjacency lists
Prim, array (dense)	O(V²)	O(V)	dense graphs, complete graphs of points

O(E log E) and O(E log V) are the same class: E ≤ V², so log E ≤ 2 log V. Union-find with path compression and union by size costs O(α(V)) per operation, where α is the inverse Ackermann function, at most 4 for any input that fits in our universe.

Variations you’ll meet

• Maximum spanning tree. Sort descending (or negate weights).
• Forced edges. Union them first (and add their weight), then run Kruskal on the rest.
• Second-best MST and “is this edge in every / some MST?”: classic follow-ups built on swapping one edge.
• Borůvka’s algorithm. Every component picks its cheapest outgoing edge in parallel; O(E log V). The basis of parallel and distributed MST.
• Euclidean MST. For points in the plane, all-pairs edges cost O(V²); fine up to a few thousand points with dense Prim.

Pitfalls

• Directed graphs. MST is defined for undirected graphs. The directed version (“minimum arborescence”) needs a different algorithm (Chu-Liu/Edmonds).
• Disconnected input. Decide what to return: the forest, -1, or an error. Check len(tree) == V - 1.
• Union-find without path compression or union by rank/size can degrade to O(V) per find.
• Sorting the wrong field. Sort by weight, not by node id; in tuples (u, v, w) the key is the last element.
• Integer overflow on large totals in C#: use long.

In the interview

• Ask: undirected? Connected? Are edges given, or is it all pairs of points (dense)? Any edges forced or free?
• Name the cut property when you justify greediness: “The cheapest edge across any cut is safe, so taking the cheapest edge that joins two components never hurts.”
• Choose by density: Kruskal for edge lists, dense Prim when every pair is an edge.
• Expected follow-ups: what if the graph is disconnected, what if some edges are already built, what if an edge’s weight changes, prove the greedy choice.

Check yourself

Check yourself

pick one

Kruskal reaches edge (c, f, 7). find(c) and find(f) return the same root. What does that mean?

Ac and f are both leavesBc and f are already connected by cheaper edges, so this edge would close a cycle: skip itCThe graph is disconnectedDTake the edge and union again

Check yourself

pick one

You have 3,000 points in the plane and the cost of linking two is their distance. Which approach fits best?

AKruskal over all ~4.5 million pairsBPrim with an array (O(V²)), computing distances on the flyCDijkstra from point 0

Check yourself

pick one

All edge weights are distinct. How many minimum spanning trees can the graph have?

AExactly oneBAt most twoCUp to V^(V−2)

Practice on your own

These are classic textbook exercises, not gym questions:

• Minimum cost to connect all points on a grid, where cost is Manhattan distance.
• Minimum cost to supply water to every house: build a well at a house or lay a pipe (hint: a virtual “well” node).
• Find all edges that appear in every MST (critical edges) and in some MST (pseudo-critical).
• Group points into k clusters maximising the minimum distance between clusters.

Go deeper

• CLRS, Introduction to Algorithms, “Minimum Spanning Trees”: the generic algorithm, the cut property (safe edges), Kruskal and Prim.
• Sedgewick and Wayne, Algorithms 4.3: Minimum spanning trees, with lazy and eager Prim.
• cp-algorithms: Kruskal with DSU and Prim.
• Tarjan, “Efficiency of a Good But Not Linear Set Union Algorithm”, JACM 1975: the α(n) bound for union-find.

Related

Union-findThe cycle check inside Kruskal.

Shortest pathsSame heap shape, different question.

Greedy algorithmsWhy exchange arguments prove greedy choices.

HeapsCheapest-edge selection in Prim.