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.
Definitions
Definition— spanning tree
A spanning tree of a connected undirected graph is a subset of its edges that connects all the vertices and contains no cycle. Every spanning tree has exactly edges. If 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 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 (so and are in the same group exactly when find(x) == find(y)), and union(x, y) merges the groups containing and .
The cut property
Every MST algorithm rests on one fact.
Theorem— Cut property
Let be any cut of a connected weighted graph, and let be a lightest edge crossing it. Then some minimum spanning tree contains . If is the unique lightest crossing edge, every minimum spanning tree contains it.
Proof
Exchange argument. Let be an MST that does not contain , with and . Since is spanning, it contains a path from to , and that path must cross the cut somewhere, along some edge . Adding to creates exactly one cycle (the path plus ); removing from that cycle leaves a graph that is again connected with edges, so it is a spanning tree . Its weight is , because is a lightest crossing edge and also crosses. So is an MST containing . If were the unique lightest crossing edge, then and would be strictly lighter than , which is impossible; so in that case every MST already contains .
∎
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 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.)
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.
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 componentsCorrectness. When the edge is added, take the cut whose one side is '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 is a lightest crossing edge, and the cut property says it is safe.
Cost. Sorting takes . The loop performs "same component?" tests and 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.
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 . 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 . 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 has at least elements in its tree. Hence every rank, and every tree's height, is at most , and find takes time.
Proof
By induction over the sequence of unions. A single element has rank 0 and element. Linking a root of smaller rank under a root of rank leaves the larger root's rank unchanged and only adds elements. Linking two roots of equal rank produces a root of rank whose tree contains both trees, so at least elements. Since a tree has at most elements, , so . A tree's height grows only in the equal-rank case, by one, exactly when its rank does, so height rank.
∎
Path compression. During find(x), once the root is known, make every node on the path from 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 operations on elements takes time, where is the inverse Ackermann function. The Ackermann function grows so explosively that its inverse is at most 4 for every that could ever be stored, or counted: the first with 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 factor. Tarjan's proof is beyond this lesson; Tarjan and van Leeuwen (1984) extend it to path halving and other variants.
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:,}")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.
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 the set of tree vertices, that edge is a lightest edge crossing the cut , 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 . 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 , which beats any method when is close to .
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))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.
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 components remain. The components are 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 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.
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")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 – of weight 2, – of weight 2 and – of weight 1, an MST is , of weight 3, in which the path from to has length 3, although the direct edge has length 2. A shortest-path tree from (, 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
1. Minimum spanning trees and union–find
Warm-upHumanAn 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
CoreHumanA 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?
3. Minimum spanning trees and union–find
CoreHumanIn a connected graph with distinct edge weights, the vertices are split into 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?
4. Minimum spanning trees and union–find
CoreHumanA 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
CoreComputationalA 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.
6. Minimum spanning trees and union–find
StretchComputationalA 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 ( 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.
7. Minimum spanning trees and union–find
CoreHumanYou 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?
Further reading and resources
- On the shortest spanning subtree of a graph and the traveling salesman problem · Joseph B. Kruskal · 1956
- Shortest Connection Networks And Some Generalizations · Robert C. Prim · 1957
- On the History of the Minimum Spanning Tree Problem · Ronald L. Graham and Pavol Hell · 1985From Borůvka's electrical network for Moravia (1926) and Jarník's reply (1930) to the algorithms of the 1950s.
- Efficiency of a Good But Not Linear Set Union Algorithm · Robert E. Tarjan · 1975The inverse-Ackermann analysis of union by rank with path compression.
- Worst-case Analysis of Set Union Algorithms · Robert E. Tarjan and Jan van Leeuwen · 1984Path halving, path splitting and other variants, all with the same bound.
- Efficient Graph-Based Image Segmentation · Pedro F. Felzenszwalb and Daniel P. Huttenlocher · 2004Kruskal-style merging with union–find, applied to the pixels of an image.
- scipy.sparse.csgraph.minimum_spanning_tree · SciPy documentation
- scipy.cluster.hierarchy.linkage · SciPy documentationHierarchical clustering; method='single' is the spanning-tree clustering of this lesson.