Skip to content
LumenaryAcademy
Algorithms 65 min

Minimum spanning trees and union–find

Connecting everything at the least cost, and a tiny data structure whose analysis meets one of the slowest-growing functions in mathematics.

Code tested · 5AI-draftedAwaiting review by a computer scientist

Your guides: Chloe · The Computer Scientist, Margaret · The Experimenter, Gideon · The Verifier

MotivationH

Connecting everything, cheaply

An archipelago government wants to connect fourteen islands with undersea fibre-optic cable, so that every island can reach every other, possibly through intermediate islands. Engineers have priced every feasible cable route. Which routes should be built to connect all the islands at the least total cost?

This is one of the oldest problems in algorithm design. In 1926 the Czech mathematician Otakar Borůvka solved it for the electricity network of southern Moravia; Vojtěch Jarník gave another solution in 1930; and the algorithms we use today were rediscovered in the 1950s by Joseph Kruskal, Robert Prim and Edsger Dijkstra, as telephone and power networks spread. The answer is always a tree: if the chosen cables contained a cycle, removing the most expensive cable of the cycle would keep everything connected and save money.

The problem has a close companion. While building the network, cable by cable, we keep asking: are these two islands already connected? Answering that question quickly, while connections keep being added, is the job of the union–find (disjoint-set) data structure. It is only a few lines of code, it runs in what is practically constant time per operation, and the proof of that fact is one of the most celebrated analyses in computer science.

DefinitionsH

Definitions

Definition— spanning tree

A spanning tree of a connected undirected graph G=(V,E)G = (V, E) is a subset of its edges that connects all the vertices and contains no cycle. Every spanning tree has exactly ∣V∣−1|V| - 1 edges. If GG is not connected, the analogous object is a spanning forest, one tree per component.

Definition— minimum spanning tree

In a graph with edge weights, a minimum spanning tree (MST) is a spanning tree whose total edge weight is as small as possible. There may be several MSTs; if all weights are distinct, the MST is unique.

Definition— cut

A cut (S,V∖S)(S, V \setminus S) splits the vertices into two non-empty groups. An edge crosses the cut if it has one endpoint on each side. A lightest crossing edge is a crossing edge of minimum weight.

Definition— disjoint-set structure

A disjoint-set (union–find) structure maintains a partition of a set of elements into disjoint groups, with two operations: find(x) returns a representative of the group containing xx (so xx and yy are in the same group exactly when find(x) == find(y)), and union(x, y) merges the groups containing xx and yy.

ABCDEF463527489
A weighted graph with its minimum spanning tree highlighted: five edges of total weight 18. Every unhighlighted edge is the heaviest edge on some cycle it would close.
ExplanationH

The cut property

Every MST algorithm rests on one fact.

Theorem— Cut property

Let (S,V∖S)(S, V \setminus S) be any cut of a connected weighted graph, and let ee be a lightest edge crossing it. Then some minimum spanning tree contains ee. If ee is the unique lightest crossing edge, every minimum spanning tree contains it.

Proof

Exchange argument. Let TT be an MST that does not contain e={u,v}e = \{u, v\}, with u∈Su \in S and v∉Sv \notin S. Since TT is spanning, it contains a path from uu to vv, and that path must cross the cut somewhere, along some edge ff. Adding ee to TT creates exactly one cycle (the path plus ee); removing ff from that cycle leaves a graph that is again connected with ∣V∣−1|V| - 1 edges, so it is a spanning tree T′=T+e−fT' = T + e - f. Its weight is w(T)+w(e)−w(f)≤w(T)w(T) + w(e) - w(f) \le w(T), because ee is a lightest crossing edge and ff also crosses. So T′T' is an MST containing ee. If ee were the unique lightest crossing edge, then w(e)<w(f)w(e) < w(f) and T′T' would be strictly lighter than TT, which is impossible; so in that case every MST already contains ee.

∎

The mirror-image cycle property says that the heaviest edge of any cycle (if it is the unique heaviest) belongs to no MST, by the same swap. Together they justify a generic greedy algorithm: start with no edges, and repeatedly add a lightest edge crossing some cut that no chosen edge crosses. Each addition is safe by the cut property, so after ∣V∣−1|V| - 1 additions we have an MST. Kruskal's and Prim's algorithms are two ways to choose the cuts. (The greedy method works here for a deep reason: spanning forests form a structure called a matroid, on which greedy algorithms are always optimal. See Greedy algorithms for the general pattern.)

ExplanationH

Kruskal's algorithm

Kruskal's algorithm considers the edges from lightest to heaviest and keeps each edge that joins two different components of the forest built so far, discarding edges that would close a cycle.

text
Kruskal(G):
    sort the edges by weight
    start with every vertex in its own component
    for each edge {u, v} in sorted order:
        if u and v are in different components:
            add {u, v} to the tree; merge the two components

Correctness. When the edge {u,v}\{u, v\} is added, take the cut whose one side is uu's current component. No chosen edge crosses this cut. Every lighter edge crossing it has already been considered, and was not discarded (a discarded edge lies inside one component, so it does not cross), so it would have been added and merged the components; hence {u,v}\{u, v\} is a lightest crossing edge, and the cut property says it is safe.

Cost. Sorting takes O(Elog⁡E)=O(Elog⁡V)O(E \log E) = O(E \log V). The loop performs EE "same component?" tests and V−1V - 1 merges. With the union–find structure below, those cost almost nothing, so sorting dominates. On the figure's graph, Kruskal takes C–F (2), A–D (3), A–B (4), E–F (4), B–E (5) and then stops, since five edges span six vertices: total 18.

ExplanationH

Union–find

The obvious way to track components is to store a label for each vertex: find is one lookup, but union must relabel one entire group, which can cost O(n)O(n). A better representation is a forest of parent pointers: each group is a tree, each element points to its parent, and the root represents the group. find(x) follows parents to the root; union(x, y) makes one root the child of the other. Unions are now cheap, but a careless sequence of unions can build a tree that is one long path, and then find costs O(n)O(n). Two small rules prevent that.

Union by rank. Give each root a rank, an upper bound on its tree's height, starting at 0. When linking two roots, attach the one of smaller rank under the one of larger rank; only when the ranks are equal does the new root's rank grow by one. (Union by size, attaching the smaller tree under the larger, works equally well.)

Theorem— Union by rank keeps trees shallow

With union by rank, a root of rank rr has at least 2r2^r elements in its tree. Hence every rank, and every tree's height, is at most log⁡2n\log_2 n, and find takes O(log⁡n)O(\log n) time.

Proof

By induction over the sequence of unions. A single element has rank 0 and 20=12^0 = 1 element. Linking a root of smaller rank under a root of rank rr leaves the larger root's rank unchanged and only adds elements. Linking two roots of equal rank rr produces a root of rank r+1r + 1 whose tree contains both trees, so at least 2r+2r=2r+12^r + 2^r = 2^{r+1} elements. Since a tree has at most nn elements, 2r≤n2^r \le n, so r≤log⁡2nr \le \log_2 n. A tree's height grows only in the equal-rank case, by one, exactly when its rank does, so height ≤\le rank.

∎

Path compression. During find(x), once the root is known, make every node on the path from xx point directly to the root. Future finds from any of them take one step. (A simpler one-pass variant, path halving, makes every node on the path point to its grandparent; it has the same guarantees.)

With both rules, Robert Tarjan proved in 1975 that any sequence of mm operations on nn elements takes O(m α(n))O(m\,\alpha(n)) time, where α\alpha is the inverse Ackermann function. The Ackermann function grows so explosively that its inverse is at most 4 for every nn that could ever be stored, or counted: the first nn with α(n)=5\alpha(n) = 5 is a tower of exponentials vastly larger than the number of atoms in the observable universe. So union–find is, for all practical purposes, constant time per operation, yet not quite: Michael Fredman and Michael Saks showed in 1989 that, in a standard model of computation, no data structure for this problem can avoid the α(n)\alpha(n) factor. Tarjan's proof is beyond this lesson; Tarjan and van Leeuwen (1984) extend it to path halving and other variants.

python
class DisjointSet:
    def __init__(self, elements):
        self.parent = {x: x for x in elements}
        self.rank = {x: 0 for x in elements}
        self.groups = len(self.parent)

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:              # path compression
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False                           # already in the same group
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx                       # attach the lower-ranked root
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        self.groups -= 1
        return True

# Islands connected one cable at a time: when is everything connected?
islands = ["Aru", "Bacan", "Buru", "Kei", "Seram", "Tanimbar", "Wetar"]
cables = [("Aru", "Kei"), ("Buru", "Seram"), ("Kei", "Tanimbar"), ("Bacan", "Seram"),
          ("Aru", "Tanimbar"), ("Wetar", "Tanimbar"), ("Seram", "Kei")]
ds = DisjointSet(islands)
for day, (a, b) in enumerate(cables, start=1):
    merged = ds.union(a, b)
    note = "" if merged else "  (already connected: this cable closes a cycle)"
    print(f"day {day}: {a}-{b}, groups left: {ds.groups}{note}")

# Why the rank rule matters: union(0, 1), union(0, 2), union(0, 3), ... on 2000 elements.
def chain_of_unions(n, by_rank):
    parent, rank, steps = list(range(n)), [0] * n, 0
    def root(x):
        nonlocal steps
        while parent[x] != x:
            x, steps = parent[x], steps + 1
        return x
    for i in range(1, n):
        a, b = root(0), root(i)
        if by_rank:
            if rank[a] < rank[b]:
                a, b = b, a
            parent[b] = a                          # the lower-ranked root goes underneath
            rank[a] += rank[a] == rank[b]
        else:
            parent[a] = b                          # naive: always hang the first root under the second
    def depth(x):
        d = 0
        while parent[x] != x:
            x, d = parent[x], d + 1
        return d
    return max(depth(x) for x in range(n)), steps

for label, flag in [("naive linking", False), ("union by rank", True)]:
    height, steps = chain_of_unions(2000, flag)
    print(f"{label:14} tallest tree: {height:5}   pointer steps during the finds: {steps:,}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Naive linking turns this innocent sequence of unions into a single path of 2000 elements, and the finds walk about two million pointers in total, a quadratic cost. With union by rank every new element is hung directly under the root: height 1, and essentially no walking at all. Path compression on top (as in the class above) repairs even the bad trees, but the rank rule is what guarantees the logarithmic bound on its own.

ExplanationH

Prim's algorithm

Prim's algorithm (found first by Jarník in 1930, then by Prim in 1957 and Dijkstra in 1959) grows a single tree from a start vertex. At each step it adds the lightest edge that leaves the tree: with SS the set of tree vertices, that edge is a lightest edge crossing the cut (S,V∖S)(S, V \setminus S), so the cut property makes it safe.

With a binary heap of candidate edges (or of vertices keyed by their cheapest connection to the tree) and lazy deletion, as in Dijkstra's algorithm, Prim runs in O(Elog⁡V)O(E \log V). The two algorithms look almost identical; the difference is the key in the heap. Dijkstra uses the total distance from the source, Prim only the weight of the single connecting edge. For dense graphs, a version with a plain array instead of a heap runs in O(V2)O(V^2), which beats any O(Elog⁡V)O(E \log V) method when EE is close to V2V^2.

python
import heapq

edges = [("A", "B", 4), ("B", "C", 6), ("A", "D", 3), ("B", "E", 5), ("C", "F", 2),
         ("D", "E", 7), ("E", "F", 4), ("B", "D", 8), ("C", "E", 9)]
vertices = sorted({v for e in edges for v in e[:2]})

def kruskal(vertices, edges):
    parent = {v: v for v in vertices}
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]          # path halving
            x = parent[x]
        return x
    tree = []
    for u, v, w in sorted(edges, key=lambda e: e[2]):
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            tree.append((u, v, w))
    return tree

def prim(vertices, edges, start):
    adj = {v: [] for v in vertices}
    for u, v, w in edges:
        adj[u].append((w, u, v))
        adj[v].append((w, v, u))
    in_tree, tree = {start}, []
    heap = list(adj[start])
    heapq.heapify(heap)
    while heap and len(in_tree) < len(vertices):
        w, u, v = heapq.heappop(heap)
        if v in in_tree:
            continue                               # stale: both ends already in the tree
        in_tree.add(v)
        tree.append((u, v, w))
        for e in adj[v]:
            if e[2] not in in_tree:
                heapq.heappush(heap, e)
    return tree

for name, tree in [("Kruskal", kruskal(vertices, edges)), ("Prim from A", prim(vertices, edges, "A"))]:
    print(f"{name:12} weight {sum(w for *_, w in tree)}:", ", ".join(f"{u}-{v}" for u, v, _ in tree))
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Both find weight 18, adding the same edges in different orders. A third classic, Borůvka's algorithm, lets every component simultaneously pick its lightest outgoing edge, halving the number of components in each round; that independence makes it the basis of parallel and distributed MST algorithms.

ExplanationH

Applications

Network design. Cables, pipelines, roads and circuit wiring that must connect given sites as cheaply as possible are MST problems, at least as a first model. Real projects add constraints (redundancy, so that one broken cable does not disconnect anyone; capacity; distance limits), and if new junction points may be added anywhere, the problem becomes the Steiner tree problem, which is NP-hard.

Clustering. Run Kruskal's algorithm on points with distances as edge weights, but stop when kk components remain. The components are kk clusters, and this is single-linkage clustering, available as method="single" in SciPy's linkage. It has a clean guarantee: among all ways to split the points into kk groups, it maximises the spacing, the smallest distance between two points in different groups (you will prove and implement this in the exercises). Its known weakness is "chaining": a thin line of points can join two otherwise separate clusters.

Image segmentation. Felzenszwalb and Huttenlocher's algorithm (2004) treats pixels as vertices and colour differences as edge weights, and merges regions in Kruskal order with union–find, using an adaptive threshold that compares the edge with the variation already inside each region. It segments a photograph in nearly linear time.

Approximation. In the travelling-salesperson problem with distances that obey the triangle inequality, walking around an MST and skipping repeated cities gives a tour at most twice the optimal length, a first example of the approximation algorithms in Hard problems.

Union–find on its own. Whenever "is connected to" or "is equivalent to" grows by merging, union–find tracks the classes (see equivalence relations): which computers can reach each other as links come up; which customer accounts belong to the same person because they share an email address or a phone number; which sites of a randomly filled grid are connected in percolation simulations; which type variables must be equal during type inference in compilers for languages such as Haskell and OCaml. Randomised Kruskal also generates mazes: shuffle the walls of a grid and knock down each wall that separates two cells not yet connected.

python
import random

def kruskal_maze(rows, cols, seed):
    """A perfect maze: exactly one path between any two cells, built with union-find."""
    rng = random.Random(seed)
    parent = list(range(rows * cols))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    walls = [(r, c, dr, dc) for r in range(rows) for c in range(cols)
             for dr, dc in ((0, 1), (1, 0)) if r + dr < rows and c + dc < cols]
    rng.shuffle(walls)
    open_walls = set()
    for r, c, dr, dc in walls:
        a, b = find(r * cols + c), find((r + dr) * cols + c + dc)
        if a != b:                                  # the wall separates two regions: knock it down
            parent[a] = b
            open_walls.add((r, c, dr, dc))
    lines = ["+" + "---+" * cols]
    for r in range(rows):
        row, below = "|", "+"
        for c in range(cols):
            row += "   " + (" " if (r, c, 0, 1) in open_walls else "|")
            below += ("   " if (r, c, 1, 0) in open_walls else "---") + "+"
        lines += [row, below]
    return "\n".join(lines), len(open_walls)

maze, opened = kruskal_maze(6, 12, seed=7)
print(maze)
print(f"{opened} walls removed for {6 * 12} cells: a spanning tree has cells - 1 = {6 * 12 - 1} edges")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.
Common misconceptionsH

Common misconceptions

Misconception

"A minimum spanning tree contains the shortest paths." It minimises the total weight, not the distance between any particular pair. In a triangle with edges ss–aa of weight 2, ss–bb of weight 2 and aa–bb of weight 1, an MST is {a–b,s–a}\{a\text{–}b, s\text{–}a\}, of weight 3, in which the path from ss to bb has length 3, although the direct edge has length 2. A shortest-path tree from ss ({s–a,s–b}\{s\text{–}a, s\text{–}b\}, weight 4) is a different object for a different goal.

Misconception

"The minimum spanning tree is unique." Only when no two edges have the same weight (more precisely, when ties never force a choice). With ties there can be many MSTs, all of the same total weight.

Misconception

"Kruskal's algorithm works on directed graphs too." The directed analogue, a minimum-weight arborescence in which every vertex is reachable from a root, is not solved by sorting edges; it needs the Chu–Liu/Edmonds algorithm, which repeatedly contracts cycles.

Misconception

"Union–find can split groups too." It only merges. Supporting deletions of edges while answering connectivity queries (fully dynamic connectivity) is much harder, and the known solutions are far more complex.

Optional Christian reflection · That they all may be one

A reflection from the Christian tradition that inspires Lumenary Academy. It is not part of the mathematics and you are welcome to skip it.

A union–find structure begins with every element alone and, merge by merge, gathers them into fewer and larger groups; the minimum spanning tree reaches everyone at the least cost. In John's Gospel, Jesus prays for his followers "that they all may be one" (John 17:21, King James Version), a unity that is not uniformity: in a spanning tree every vertex keeps its own place and its own connections. It is a pleasant thought that one of the most efficient structures in computer science is about joining what was separate, and a sober one that, unlike people, it can never undo a mistaken union.

Exercises

Exercises

1. Minimum spanning trees and union–find

Warm-upHuman

An undirected graph on the vertices P, Q, R, S, T has these edges:

Edge Weight Edge Weight
P–Q 3 R–S 6
P–R 1 R–T 5
Q–R 4 S–T 7
Q–S 2

What is the total weight of a minimum spanning tree?

2. Minimum spanning trees and union–find

CoreHuman

A town council builds a minimum spanning tree of footpaths between five villages, minimising the total length of path to build. A resident says: "Good, now the walk from my village to every other village is as short as it can be." Is that right?

Choose one

3. Minimum spanning trees and union–find

CoreHuman

In a connected graph with distinct edge weights, the vertices are split into S={A,B,C}S = \{A, B, C\} and the rest. Exactly three edges cross this cut: C–D of weight 9, A–E of weight 4 and B–F of weight 6. What can you conclude?

Choose one

4. Minimum spanning trees and union–find

CoreHuman

A union–find structure with union by rank (and no other optimisation) holds 1000 elements. Whatever sequence of unions is performed, what is the largest rank any root can reach?

5. Minimum spanning trees and union–find

CoreComputational

A rural internet project connects n villages, numbered 0 to n - 1. On day 1 the link links[0] (a pair of villages) is switched on, on day 2 the link links[1], and so on; links work both ways.

Write first_day_connected(n, links) that returns the first day on which every village can reach every other (through any chain of links), or -1 if that never happens. A single village is connected from the start, on day 0. Use a union–find structure so that the whole computation is nearly linear in the number of links.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

6. Minimum spanning trees and union–find

StretchComputational

A field biologist has GPS positions of birds' nests and wants to split them into exactly k colonies so that the colonies are as well separated as possible. The spacing of a split is the smallest distance between two nests in different colonies.

Write max_spacing(points, k) that returns the largest possible spacing over all ways to split the distinct points into exactly k non-empty groups (2≤k≤2 \le k \le len(points)), using Euclidean distance (math.dist).

Approach: run Kruskal's algorithm on all pairs of points with their distances as weights, but stop as soon as only k components remain. The answer is the length of the next edge Kruskal would have used to merge two components.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

7. Minimum spanning trees and union–find

CoreHuman

You need a minimum spanning tree of a complete graph on 5000 points (every pair of points is joined by an edge, about 12.5 million edges), with the weights computed on demand from the points' coordinates. Which approach has the best worst-case running time?

Choose one

Further reading and resources