Gregory Friedman The Greg Wide Web on the name →
The Arc · lecture XIV of XIV

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 (u,v)(u, v) closes a cycle exactly when uu and vv 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) puts x in a group of its own. We will do all of these up front, in the constructor.
  • find(x) returns a representative of x’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 containing x and y into 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 O(1)O(1), 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. O(n)O(n) per union, and n−1n - 1 unions to merge everything, so O(n2)O(n^2) overall.

python runs in your browser · first run downloads ~240 kb
Plate I The labelling approach, and the wall it hits. `find` costs one lookup, which is optimal. But the union column grows quadratically: doubling nn from 80 to 160 takes the work from about 6,400 to about 25,600, a factor of four. This is exactly the shape Lecture III taught you to recognise and refuse, and the rest of the lecture is about refusing it.

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 O(1)O(1) 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.

python runs in your browser · first run downloads ~240 kb
Plate II The forest, and the adversary that ruins it. Merging in the order (1,0), then (2,1), then (3,2), and so on, hangs each new root under the previous one and builds a single chain twelve deep. `union` is now O(1)O(1), but `find` on the deepest element walks eleven pointers. We have not removed the quadratic behaviour, we have moved it from `union` to `find`. Note that this input is not pathological or unlikely; it is what you get from merging things in order, which is what Kruskal does constantly.

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 hh contains at least 2h2^h elements. Prove it by induction on the number of unions. A single element has height 0 and 20=12^0 = 1 element, so the base case holds. When we merge trees AA and BB with ∣A∣≥∣B∣|A| \ge |B|, hanging BB under AA‘s root, the result has height max⁡(hA, hB+1)\max(h_A,\, h_B + 1). If the max is hAh_A the tree only got bigger and the claim still holds. If the max is hB+1h_B + 1, then the merged tree has ∣A∣+∣B∣≥2∣B∣≥2⋅2hB=2hB+1|A| + |B| \ge 2|B| \ge 2 \cdot 2^{h_B} = 2^{h_B + 1} elements. Either way the invariant survives.

So a tree of nn elements has height at most log⁡2n\log_2 n, and find is O(log⁡n)O(\log n). 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.

python runs in your browser · first run downloads ~240 kb
Plate III Both fixes, on two workloads chosen to separate them. Workload A is the chain from Plate II: union by size alone collapses it from 2,016 hops to 124, and path compression then has nothing left to repair. Workload B merges in a doubling pattern, which is the one shape that defeats union by size, and there the roles reverse exactly: naive and by-size are identical at height 6, and compression is what drops the hops from 576 to 246. Neither optimisation alone is enough for every input, which is the real reason the structure carries both. The scaling table is the honest form of the claim: nlog⁡nn \log n against something that stays near 4n4n.

How fast is it, really?

With both optimisations, mm operations on nn elements cost O(m α(n))O(m \, \alpha(n)), where α\alpha 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 A(m,n)A(m, n) grows faster than any primitive recursive function. Along the diagonal that α\alpha inverts, A(1,1)=3A(1,1) = 3, A(2,2)=7A(2,2) = 7, A(3,3)=61A(3,3) = 61, and A(4,4)A(4,4) is a tower of powers of two past anything writable; even one step down, A(4,2)=265536−3A(4,2) = 2^{65536} - 3 already has roughly nineteen thousand digits. Its inverse α(n)\alpha(n) therefore grows more slowly than any function you would think to write down. For every nn below A(4,4)A(4,4), which is to say for every input that will ever exist, α(n)≤4\alpha(n) \le 4.

python runs in your browser · first run downloads ~240 kb
Plate IV Why "essentially constant" is a fair description and still not the same as constant. The first block computes the diagonal A(m,m)A(m,m) for the first few mm and stops before A(4,4)A(4,4), which is a tower of powers of two and would not finish. The second lists the thresholds of the inverse: α(n)≤4\alpha(n) \le 4 for every nn below A(4,4)A(4,4). The bound is not O(1)O(1), and Fredman and Saks proved in 1989 that no implementation can be, but the gap is unobservable.

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.

python runs in your browser · first run downloads ~240 kb
Plate V Kruskal, every decision shown. Eleven edges in weight order, each marked take or REJECT, then the resulting tree. Six edges taken for seven vertices, as any spanning tree must have. Every rejection is a cycle that union-find detected in essentially constant time; there is no separate cycle-checking code anywhere in the algorithm, because `union` returning False is the cycle test.

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.

python runs in your browser · first run downloads ~240 kb
Plate VI Kruskal and Prim on one graph, edge by edge. Same total weight (35) and, because every edge weight here is distinct and the minimum spanning tree is therefore unique, the same set of edges. The orders disagree completely: Kruskal opens with the globally cheapest edge in the graph, B-E at 3, which is nowhere near Prim's start vertex; Prim opens with the cheapest edge touching A. If you edit the weights so that two edges tie, the set equality can fail while the total stays equal, which is the correct and slightly weaker claim.

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

4893621271151011413151617ABCDEFGHIJ

The order each algorithm added them

Kruskal and Prim on the same graph: the edges each added, in the order it 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

Pointer hops charged by find during Kruskal's run, and the tallest tree reached, for each union strategy with path compression off and 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.

Plate VII Above, the disjoint-set forest: union elements and watch the roots re-point, call find and watch a path either climb or collapse. The path-compression toggle and the union-strategy control change the shape of the forest, and the running counters (total find hops, current maximum height) are the argument for the optimisations stated in numbers rather than asserted. Below, Kruskal against Prim on one graph, stepped edge by edge, with Kruskal's rejected edges marked and the two running totals converging on the same number by different routes. Step advances one operation; reduced motion jumps to the finished state.

What it costs

For nn elements and mm operations:

Structurefindunionn−1n-1 unions plus nn finds
Label arrayO(1)O(1)O(n)O(n)O(n2)O(n^2)
Forest, naive unionO(n)O(n)O(1)O(1) plus two findsO(n2)O(n^2)
Forest, union by sizeO(log⁡n)O(\log n)O(log⁡n)O(\log n)O(nlog⁡n)O(n \log n)
Forest, compression onlyamortised O(log⁡n)O(\log n)sameO(nlog⁡n)O(n \log n)
Forest, bothamortised O(α(n))O(\alpha(n))sameeffectively O(n)O(n)

And for the two spanning-tree algorithms on a graph with nn vertices and mm edges:

AlgorithmTimeDominated by
Prim, binary heapO(mlog⁡n)O(m \log n)the heap operations
Kruskal, union-findO(mlog⁡m)O(m \log m)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 O(m)O(m) 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.

  1. On paper, the bound. Prove by induction that with union by size, any tree of height hh contains at least 2h2^h elements, and conclude that find is O(log⁡n)O(\log n). Then answer the sharper question: is that bound tight? Either exhibit a sequence of unions that actually produces a tree of height ⌊log⁡2n⌋\lfloor \log_2 n \rfloor, or prove none exists.

  2. On paper, the accounting. Path compression makes a single find no cheaper in the worst case: the first find on 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.

  3. 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 sorted in 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.

  4. The structure itself. Implement find with path compression and union by size. find must leave every node on the walked path pointing directly at the root; union must hang the smaller tree under the larger and return True only 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 kb
    Plate 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

    find in two passes. First walk root up until self._parent[root] == root. Then walk x up again, and for each node on the way set its parent to root before moving on. Save the next pointer before you overwrite it, or you will lose your place on the path.

    Hint two

    union starts by calling find on both arguments. If the roots are equal, return False immediately and change nothing. Otherwise compare self._size at the two roots, swap your names for them if needed so that a is the larger, then set self._parent[b] = a and add b’s size into a’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 True

    The line a, b = b, a is 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 that self._size is meaningful only at a root; the values left behind at non-roots are stale and nothing reads them.

  5. Kruskal. Write kruskal(V, E) returning (taken, rejected), both in the order the algorithm encountered them. A working UnionFind is 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 kb
    Plate 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 to taken, else appends to rejected. That really is the whole function.

    Hint two

    You do not need to stop early once you have len(V) - 1 edges, though you may; the remaining edges will all be rejected anyway. If you do stop early, the rejected list 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, rejected

    Notice what is not here: no visited set, no cycle detection, no check of how many edges have been taken. union returning False carries all of that. Notice too that the algorithm never looks at V except 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.

Keys on this page

A figure's keys are its own: they answer once the figure has focus, so tab to it or click it first. Esc closes this sheet.