Union-Find Visualizer

Some questions are asked so often that the cost of answering them decides whether a program is fast or slow. Is this cable already linked to that one? Do these two pixels belong to the same blob? Would this road close a loop in the network I am building? Each is the same question in different clothes: are these two things connected yet, given everything joined so far?

The obvious answer is to keep a label on every item and rewrite labels when two groups merge. It works, and it is honest, but a merge can touch every item in the smaller group or, done carelessly, every item there is. The disjoint-set structure, also called union-find or a merge-find set, turns the problem around. It never relabels anything. It lets each item point at one other item, and lets the pointers do the work.

A forest that points upward

Picture every item as a node with a single arrow leading to its parent. Follow the arrows and you climb a tree until you reach a node whose arrow points at itself. That node is the root, and the root is the name of the set. Two items are connected exactly when their climbs end at the same root. A whole collection of sets is therefore a forest, one tree per set, stored as nothing more than an array of parent numbers.

The structure needs only three operations. Make-set adds an item that points at itself. Find climbs from an item to its root. Union finds the two roots and points one at the other, which merges two trees with a single write. Bernard Galler and Michael Fischer described this tree structure in 1964, in a paper about assigning storage for program declarations; their abstract notes that the method applies to any problem that must identify equivalence classes from pairs.

The catch is in the word climbs. A find costs one hop for every arrow on the way up, and nothing in the bare idea stops the trees from growing tall. Union item 0 with item 1, then 1 with 2, then 2 with 3, always hanging the first tree under the second, and you build a chain. With 16 items, a find from the bottom of that chain takes 15 hops. With a million, it takes a million minus one, and the clever structure is no better than a list.

Two rules that keep the trees low

The first rule is about which root goes on top. Union by size keeps a count of descendants in every root and hangs the smaller tree under the larger. Union by rank keeps a rank instead, an upper bound on height, and hangs the lower rank under the higher; only when two ranks tie does the winner’s rank go up by one. Either way the tall tree stays the root, and the short one adds at most a single level.

That rule alone bounds the height. Every rank stays at or below floor(log2 n), and a root of rank r sits on top of at least two to the power r nodes, because a rank only rises when two equal trees meet. Union by size gives the same guarantee by a doubling argument: an item only moves one level deeper when its tree joins one at least as large, so its tree at least doubles each time. For a thousand items no find ever needs more than nine hops, and the tool checks this for every n from 1 to 1,024.

The second rule works during the find. Once you have climbed to the root, you already know where every node on the way belongs, so you may as well tell them. Full path compression sends a second pass up the same path and points every node straight at the root. Path splitting does it in one pass by pointing each node at its grandparent as you go. Path halving does the same for every other node. None of these moves a node to another set; each only shortens the road to the root it already had.

Splitting and halving are one-pass methods. In their 1984 worst-case analysis of many variants of path compression, Robert Tarjan and Jan van Leeuwen showed that two one-pass methods are asymptotically optimal, while several other proposed variants are slower than the best. That is the practical attraction: no stack, no second pass, and no loss in the bound.

The bound that made the structure famous

Put the two rules together and the cost of a long sequence of operations becomes almost linear. John Hopcroft and Jeffrey Ullman bounded it in 1973 by a constant times n G(n), where G grows more slowly than any fixed number of nested logarithms. In 1975 Robert Tarjan pinned it down exactly. For a long run of m finds mixed with n minus 1 unions, he proved that the worst-case time lies between two constant multiples of m times alpha(m, n), where alpha is related to a functional inverse of Ackermann’s function.

Ackermann’s function grows so violently that its inverse barely moves. The NIST Dictionary of Algorithms and Data Structures defines the two-parameter version as the smallest i of at least 1 for which A(i, floor(m/n)) exceeds log2 n, and notes that it is not strictly an inverse; it simply grows as slowly as Ackermann’s function grows quickly. For any n that could actually be written down in the physical universe, alpha is 4 or less. Later work showed the bound is tight for pointer algorithms of this kind, and that no disjoint-set structure can do better per operation in the model Fredman and Saks studied in 1989.

There is a temptation here that the tool refuses on purpose. You cannot see alpha. At a thousand elements or a billion, a function that stays below 5 is indistinguishable from a constant, so any curve that claims to show it is decoration. The tool shows what can be measured instead: the hops.

Here is a worked example you can reproduce. Open the tool, keep the Sequence seed at 7 and read the Rules compared table. One seeded workload on 1,024 elements runs 3,072 unions of random pairs, each followed by a find, then joins whatever is left and runs 1,024 more finds: 12,286 finds in all. With the naive union and no compression, the average find costs 86.92 hops and the longest costs 181, because the trees grow into ragged chains. With union by size and full path compression, the same operations average 0.90 hops, the longest find costs 4 and the final tree has height 1.

The gap from 86.92 to 0.90 is the whole story in two numbers. Notice also what each rule contributes alone. Union by size without compression already averages 1.64 hops with a final height of 5, inside the bound of 10. Compression without a union rule averages 1.62. Each rule nearly does the job; together they leave almost nothing to do.

The opening example in the tool shows the mechanism at a size you can read. Sixteen elements are joined by union by size in rounds of equal trees, the worst case the rule allows, and element 15 ends at depth 4, exactly floor(log2 16). Its find takes 4 hops, and path compression then rewrites three pointers so that 15, 14 and 12 point straight at the root. The next find from 15 costs one hop.

Kruskal’s algorithm, the textbook use

The best-known customer for union-find is the minimum spanning tree. Given a weighted graph, you want the cheapest set of edges that connects every vertex without a cycle. Joseph Kruskal published his method in 1956: sort the edges by weight and walk through them from the lightest, keeping an edge whenever its two ends are not yet connected. The NIST dictionary puts it as keeping a set of partial trees and repeatedly adding the shortest edge whose ends lie in different ones.

That test is precisely a find on each end. If the roots differ, the edge is taken and a union merges the two trees; if they match, the edge would close a cycle and is skipped. Sorting dominates the running time, and the union-find work on the sorted edges adds only about alpha per operation. On the tool’s seeded graph of nine vertices and sixteen edges, Kruskal takes eight edges for a total weight of 23 and skips the other eight.

Prim’s algorithm reaches the same weight from the opposite direction, which is why the tool runs it separately as a check. It grows one tree from a starting vertex and repeatedly adds the cheapest edge from the tree to a vertex outside it. The method goes back to Vojtech Jarnik in 1930 and was published again by Robert Prim in 1957 and by Edsger Dijkstra in 1959. It shares no code with the forest in the tool, so when both report 23 the agreement means something.

Equal weights deserve a sentence of honesty. When every weight is distinct the minimum spanning tree is unique, and the two algorithms must choose the same edges. When weights tie, there can be several minimum trees of the same total, and Kruskal and Prim may pick different ones. Their totals still agree, which is what the tool compares, and it states the tie rule each one uses. On a graph that falls apart into pieces, both return a spanning forest: one minimum tree per connected component.

The same loop without weights counts components. Start with every vertex alone and add edges as they arrive; each successful union lowers the count by one. Tracking components this way takes amortized time proportional to alpha per operation, and it is the incremental connectivity that Kruskal’s algorithm quietly relies on.

What it cannot do

Union-find only ever merges. It has no operation that splits a set, so if an edge is deleted the forest cannot simply forget it.

Graphs that lose edges as well as gain them need dynamic connectivity structures, which cost a polylogarithmic amount per change instead of nearly nothing.

It answers whether, never how. A find tells you two items share a root; it does not give you the path between them in the original graph, because the pointers are bookkeeping and not edges of the graph. And the famous bound is amortized: a single find can still be slow if it is the one that pays for flattening a tall path, even though the sequence as a whole is cheap. The tool counts hops, not nanoseconds, and leaves cache effects and memory layout to a profiler.

Within those limits, few data structures give so much for so little. An array of integers, two rules a child could follow, and the question that started it all, are these two connected yet, costs about one hop.