Lecture XIV · Data Structures & Algorithms
Disjoint sets and Kruskal
The last lecture ended with Prim’s algorithm growing a minimum spanning tree one vertex at a time, always reaching for the cheapest edge leaving the tree it had built so far. There is an obvious alternative that Prim rules out and that ought to work: forget growing a single tree, just sort every edge in the graph by weight and take them cheapest first, skipping any edge that would close a cycle.
That is Kruskal’s algorithm, it is correct, and it is about four lines. The only difficulty in the whole thing is the phrase “would close a cycle”. Adding edge closes a cycle exactly when and are already connected by the edges taken so far. So Kruskal needs a structure that answers one question, over and over, while the answer keeps changing:
Are these two things in the same group yet?
This lecture builds that structure. It turns out to be the fastest interesting data structure in the course, and pinning down exactly how fast requires a function most people never meet.
The ADT
A disjoint-set structure (also called union-find, which describes it better) maintains a partition of some elements into groups. Three operations:
makeset(x)putsxin a group of its own. We will do all of these up front, in the constructor.find(x)returns a representative ofx’s group: some element of that group, and crucially the same one for every member of the group.union(x, y)merges the two groups containingxandyinto one.
Everything follows from noticing that we never need to list a group. We only
need to compare: x and y are together exactly when
find(x) == find(y). Not being able to enumerate a group is what buys the
speed, in the same way that not being able to ask a heap for its third-smallest
item is what bought that speed in Lecture XII.
Attempt 1: just label everything
The direct approach. Give every element a label, and say two elements are
together when their labels match. find is a dictionary lookup, so it is
, and you cannot beat that.
union(x, y) is where it falls apart. To merge group b into group a you
must find every element labelled b and relabel it, and that means touching
every element in the structure. per union, and unions to merge
everything, so overall.
Attempt 2: stop relabelling, start pointing
The waste is obvious once you name it: relabelling rewrites information that was
already correct. Every element of group b already agreed on their label; we
just changed all of them to agree on a different one.
So do not store the answer at every element. Store a pointer to somewhere
closer to the answer, and let find follow the pointers. Each group becomes a
tree, drawn with edges pointing up toward a root, and the root is the group’s
representative. This forest of up-trees is nothing like a binary search tree:
there is no ordering, no balance condition, no bound on the number of children,
and children have no idea who their siblings are. A node knows only its parent.
Now union is genuinely once you have the two roots: point one root at
the other. And find costs the depth of the element.
That last sentence contains the new problem.
The two fixes
There are two independent repairs, and the pleasing thing is that either one alone rescues the structure, while both together do something better than either.
Union by size
The chain in Plate II was built by always hanging the first root under the second, regardless of what the trees looked like. Instead, hang the smaller tree under the root of the larger one.
This gives a clean bound. Claim: with union by size, every tree of height contains at least elements. Prove it by induction on the number of unions. A single element has height 0 and element, so the base case holds. When we merge trees and with , hanging under ‘s root, the result has height . If the max is the tree only got bigger and the claim still holds. If the max is , then the merged tree has elements. Either way the invariant survives.
So a tree of elements has height at most , and find is
. Worth noting that union by rank (track height instead of size)
gives the same bound by nearly the same argument; the two are interchangeable in
practice and size is easier to keep correct.
Path compression
The second fix is opportunistic and, on its face, greedy in a way that should
not work. When find(x) walks from x up to the root, it learns the root of
every node it passed. So on the way back down, re-point every one of them
directly at the root.
The next find on any of those nodes costs one hop. This is memoization, in the
same sense as Lecture VII’s dynamic programming: the walk computed a result, and
rather than throwing it away we write it down where it will be looked for.
The cost is that find is no longer a read-only operation, which surprises
people and occasionally matters: you cannot share a union-find between threads
without a lock even if every thread only calls find.
How fast is it, really?
With both optimisations, operations on elements cost , where is the inverse Ackermann function. This is one of the strangest results in algorithms and it is worth being precise rather than hand-wavy about it.
The Ackermann function grows faster than any primitive recursive function. Along the diagonal that inverts, , , , and is a tower of powers of two past anything writable; even one step down, already has roughly nineteen thousand digits. Its inverse therefore grows more slowly than any function you would think to write down. For every below , which is to say for every input that will ever exist, .
The honest summary: union-find with both optimisations is not constant time, the proof that it cannot be is genuinely deep, and no program will ever notice the difference. Treat it as constant when you are budgeting, and know that you are rounding.
Kruskal, at last
Now the payoff. Kruskal’s algorithm in full:
def kruskal(V, E):
uf = UnionFind(V)
taken = []
for u, v, w in sorted(E, key=lambda e: e[2]):
if uf.union(u, v): # returns False if already connected
taken.append((u, v, w))
return taken
Four lines, and one of them is the sort. Note the small elegance: union
already has to call find on both arguments to do its job, and it already knows
whether they matched. So union returning a boolean gives us the cycle test for
free, with no second lookup.
Correctness rests on the same cut property that justified Prim. At any point, the taken edges form a forest. When we consider the cheapest remaining edge that joins two different components, consider the cut separating one of those components from everything else: our edge is the cheapest edge crossing that cut (anything cheaper was already considered, and would have been taken or would have been inside a component), so some minimum spanning tree contains it.
The same tree, built backwards
Prim and Kruskal solve the same problem by opposite strategies. Prim keeps one tree and grows it locally, always taking the cheapest edge leaving what it has. Kruskal keeps a scattered forest and works globally, always taking the cheapest edge left anywhere.
When all the edge weights are distinct, the minimum spanning tree is unique, so the two must end up with the identical set of edges. They cannot end up with the same order, because their whole difference is which edge looks best next. When weights tie, the MST need not be unique and the two algorithms may return genuinely different trees of equal total weight, which is why the plate below uses distinct weights and says so.
The plate: the forest and the two trees
The figure for this lecture puts both halves in one place. The top half is the disjoint-set forest itself, drawn as actual up-trees: union two elements and watch a root get re-pointed, call find and watch the path either walk slowly to the root or collapse onto it. Turn path compression off and build the chain by hand, and the counters will show you the cost you just accepted.
The bottom half runs Kruskal and Prim on the same weighted graph, side by side,
with each algorithm’s next edge highlighted before it is committed. The edges
Kruskal rejects are marked, and each rejection is a find that came back equal.
The minimum spanning tree · 10 places, 17 roads, 9 kept
The order each algorithm added them
| # | Kruskal | w | Prim from A | w |
|---|---|---|---|---|
| 1 | G–H | 1 | A–B | 4 |
| 2 | C–G | 2 | B–F | 3 |
| 3 | B–F | 3 | F–G | 5 |
| 4 | A–B | 4 | G–H | 1 |
| 5 | F–G | 5 | C–G | 2 |
| 6 | C–D | 6 | C–D | 6 |
| 7 | E–F | 7 | E–F | 7 |
| 8 | F–I | 10 | F–I | 10 |
| 9 | H–J | 13 | H–J | 13 |
| total | 51 | 51 |
Rejected by Kruskal, each one caught by a pair of finds coming back with the same root: A–E · 8 · B–C · 9 · E–I · 11 · D–H · 12 · G–J · 14 · I–J · 15 · B–E · 16 · C–F · 17. Lazy Prim discarded 4 stale fringe edges, using nothing but a flag per vertex.
What the union-find bill depends on
| union | hops, no compression | tallest | hops, compressed | tallest |
|---|---|---|---|---|
| arbitrary | 45 | 5 | 33 | 3 |
| by height | 24 | 2 | 21 | 2 |
| by weight | 24 | 2 | 21 | 2 |
Same tree every time, total weight 51: the strategies change what the bookkeeping costs, never the answer. With JavaScript enabled the forest above becomes drawable, the switches become live, and the two algorithms step through the graph side by side.
What it costs
For elements and operations:
| Structure | find | union | unions plus finds |
|---|---|---|---|
| Label array | |||
| Forest, naive union | plus two finds | ||
| Forest, union by size | |||
| Forest, compression only | amortised | same | |
| Forest, both | amortised | same | effectively |
And for the two spanning-tree algorithms on a graph with vertices and edges:
| Algorithm | Time | Dominated by |
|---|---|---|
| Prim, binary heap | the heap operations | |
| Kruskal, union-find | the sort, not the union-find |
Read the last row carefully, because it is the joke at the end of the lecture. We
have spent the whole thing building a structure so fast that its running time
needs the inverse Ackermann function to describe, and then used it in an
algorithm whose cost is dominated by the sorted call on the first line. If the
edges arrive already sorted, or can be sorted in linear time because the weights
are small integers, Kruskal is effectively and the union-find is finally
the bottleneck. Otherwise the sort is.
That is not a reason to skip the optimisations. It is a reminder of something Lecture III kept insisting on: the cost of a program is the cost of its most expensive part, and knowing which part that is matters more than making any single part fast.
Where you meet this again
Union-find is the answer whenever the question is “are these two things
connected yet” and the connections only ever get added. Connected components in
a graph, image segmentation by merging adjacent pixels, cycle detection while
building any spanning structure, type unification in a compiler’s inference
engine, and percolation models in physics all reduce to it. The condition to
watch for is that edges are only ever added: union-find has no split, and
adding one is a genuinely harder problem.
This is the last lecture of the course. What it leaves you with is the same thing the first one did: pick the contract first, implement it second, and measure the result rather than assuming it. Every structure here was invented by someone who refused to accept a quadratic.
Problems
Work these in order. The last two run their own checks; make every row green.
On paper, the bound. Prove by induction that with union by size, any tree of height contains at least elements, and conclude that
findis . Then answer the sharper question: is that bound tight? Either exhibit a sequence of unions that actually produces a tree of height , or prove none exists.On paper, the accounting. Path compression makes a single
findno cheaper in the worst case: the firstfindon a deep node still walks the whole path. Explain in a short paragraph why the structure is nevertheless fast over a long run of operations, using the word “amortised” correctly, and say what the compression is buying with the extra work it does. Then identify the one situation in which path compression is a pure loss, and be concrete about what the workload looks like.On paper, the two trees. Take the graph from Plate VI and change the weight of edge C-E from 5 to 3, so that it ties with B-E. Work out by hand whether the minimum spanning tree is still unique. If it is not, exhibit two distinct trees of equal minimum weight and say which one Kruskal finds, given that
sortedin Python is stable and the edge list order is the one printed in the plate. This is a question about your tie-break, and the fact that it has an answer at all is a property of the implementation, not of the mathematics.The structure itself. Implement
findwith path compression andunionby size.findmust leave every node on the walked path pointing directly at the root;unionmust hang the smaller tree under the larger and returnTrueonly when a merge actually happened. The checks verify the union return value, transitivity, the union-by-size direction, that compression really did flatten the path, and finally agreement with a brute-force reference over four hundred randomised merges.The checks · run against your code
uf = UnionFind(range(10)) # every element starts alone assert uf.find(3) == 3 assert not uf.connected(0, 1) # a union joins exactly two groups, and reports that it did assert uf.union(0, 1) is True assert uf.connected(0, 1) # a second union of the same pair changes nothing and says so assert uf.union(0, 1) is False assert uf.union(1, 0) is False # connectivity is transitive uf.union(1, 2) assert uf.connected(0, 2) assert not uf.connected(0, 3) # the group count is right after a chain of merges uf2 = UnionFind(range(10)) for i in range(9): uf2.union(i, i + 1) assert len({uf2.find(i) for i in range(10)}) == 1 # union by size: merging a big group with a lone element must keep the # big group's root, so the tree does not get taller uf3 = UnionFind(range(8)) for i in range(1, 6): uf3.union(0, i) # a group of six around one root big = uf3.find(0) uf3.union(6, 0) # a singleton joining the big group assert uf3.find(6) == big # path compression: after one find, everything on the path is a direct child uf4 = UnionFind(range(6)) for i in range(5): uf4.union(i + 1, i) uf4.find(5) r = uf4.find(5) for x in range(6): assert uf4._parent[x] == r or x == r # it agrees with a brute-force reference over a long random-ish run ref = {x: x for x in range(30)} uf5 = UnionFind(range(30)) seed = 12345 for step in range(400): seed = (1103515245 * seed + 12345) % 2147483648 a = seed % 30 seed = (1103515245 * seed + 12345) % 2147483648 b = seed % 30 uf5.union(a, b) la, lb = ref[a], ref[b] if la != lb: for k in ref: if ref[k] == lb: ref[k] = la for k in range(30): pass for a in range(30): for b in range(30): assert uf5.connected(a, b) == (ref[a] == ref[b])python runs in your browser · first run downloads ~240 kbPlate VIII Union-find, graded. Nine checks, of which two are the interesting ones. The union-by-size check merges a singleton into a group of six and requires the big group's root to survive, which fails immediately if you always hang the first argument under the second. The compression check walks a six-deep chain once and then requires every element to be a direct child of the root. The last check is the real one: four hundred randomised unions against an explicit label array that is recomputed the slow way. Hint one
findin two passes. First walkrootup untilself._parent[root] == root. Then walkxup again, and for each node on the way set its parent torootbefore moving on. Save the next pointer before you overwrite it, or you will lose your place on the path.Hint two
unionstarts by callingfindon both arguments. If the roots are equal, returnFalseimmediately and change nothing. Otherwise compareself._sizeat the two roots, swap your names for them if needed so thatais the larger, then setself._parent[b] = aand addb’s size intoa’s.The solution
Two passes up, and a size comparison:
def find(self, x): root = x while self._parent[root] != root: root = self._parent[root] while self._parent[x] != x: nxt = self._parent[x] self._parent[x] = root x = nxt return root def union(self, x, y): a, b = self.find(x), self.find(y) if a == b: return False if self._size[a] < self._size[b]: a, b = b, a self._parent[b] = a self._size[a] += self._size[b] return TrueThe line
a, b = b, ais the whole of union by size, and leaving it out is the single most common bug in this structure, because everything still works: the answers stay correct and only the speed quietly collapses. That is the worst kind of bug, and it is exactly why the plate above counts hops rather than just checking output. Note also thatself._sizeis meaningful only at a root; the values left behind at non-roots are stale and nothing reads them.Kruskal. Write
kruskal(V, E)returning(taken, rejected), both in the order the algorithm encountered them. A workingUnionFindis provided, so the only thing being tested is whether you understand that the cycle test is the union. Do not write a separate cycle check.The checks · run against your code
taken, rejected = kruskal(V, EDGES) # a spanning tree of 7 vertices has exactly 6 edges assert len(taken) == len(V) - 1 == 6 # nothing is lost: every edge was either taken or rejected, exactly once assert len(taken) + len(rejected) == len(EDGES) assert sorted(taken + rejected) == sorted(EDGES) # the total weight is the known minimum for this graph assert sum(w for _, _, w in taken) == 35 # edges are considered cheapest first, so the taken list is non-decreasing ws = [w for _, _, w in taken] assert ws == sorted(ws) # the very cheapest edge in the graph is always safe, so it is always taken assert ("B", "E", 3) in taken # the most expensive edge here closes a cycle and must be rejected assert ("D", "E", 15) in rejected # the result is connected: one union-find group covers everything check = UnionFind(V) for u, v, w in taken: check.union(u, v) assert len({check.find(v) for v in V}) == 1 # and acyclic: adding any taken edge to a fresh structure never fails fresh = UnionFind(V) for u, v, w in taken: assert fresh.union(u, v) is True # every rejected edge really would have closed a cycle done = UnionFind(V) for u, v, w in taken: done.union(u, v) for u, v, w in rejected: assert done.connected(u, v)python runs in your browser · first run downloads ~240 kbPlate IX Kruskal, graded, with the structural checks doing the real work. Beyond the edge count and the known minimum of 35, three properties are verified that no amount of guessing satisfies: the taken edges connect everything (one union-find group at the end), they are acyclic (re-adding them to a fresh structure never reports a duplicate), and every rejected edge genuinely has both endpoints connected in the final tree. Together those three are the definition of a spanning tree, checked rather than assumed. Hint one
sorted(E, key=lambda e: e[2])puts the edges in weight order. Then one loop:if uf.union(u, v)appends totaken,elseappends torejected. That really is the whole function.Hint two
You do not need to stop early once you have
len(V) - 1edges, though you may; the remaining edges will all be rejected anyway. If you do stop early, therejectedlist will be short and the check that every edge was accounted for exactly once will fail, so for this exercise let the loop run to the end.The solution
The sort, then one pass:
def kruskal(V, E): uf = UnionFind(V) taken, rejected = [], [] for u, v, w in sorted(E, key=lambda e: e[2]): if uf.union(u, v): taken.append((u, v, w)) else: rejected.append((u, v, w)) return taken, rejectedNotice what is not here: no visited set, no cycle detection, no check of how many edges have been taken.
unionreturningFalsecarries all of that. Notice too that the algorithm never looks atVexcept to build the structure, which is why Kruskal handles a disconnected graph gracefully and returns a spanning forest instead of failing, in contrast to Prim, which would have to be restarted from each component.