Data Structures and Algorithms with C · Lecture Notes
Chapter 16: Sets and Union-Find
Many problems reduce to the same two questions: do two items belong to the same group, and if not, how are the two groups merged into one? Network connectivity, counting components in a graph, equivalence declarations and building a minimum spanning tree ask these questions millions of times. The structure that keeps sets with no common elements and supports only these two operations is called union-find. This chapter represents the sets as trees linked from child to parent and stores the whole forest in a single integer array. It shows step by step which sequence of operations turns the first version into a chain and how the cost climbs to O(n²). Two improvements follow: the weighting rule, which bounds the tree depth by ⌊lg m⌋ + 1, and the collapsing rule, which hooks the find path directly to the root. Together they bring the cost per operation down to a factor that, because of the inverse Ackermann function, never exceeds 4 in practice. For every routine the chapter gives the C code, a line-by-line walkthrough, a code trace, a measurement and a complexity analysis.
Learning outcomes
- Model
- Represent pairwise disjoint sets as trees whose root is the set name and whose links run from child to parent.
- Implement
- Write the
findandunionroutines with a single parent array; build the array withmallocand release it withfree. - Find the worst case
- Show which sequence of operations turns the tree into a chain and why the total cost is O(n²).
- Improve
- Apply the weighting rule and the collapsing rule; interpret the depth lemma together with its proof.
- Analyze
- Explain the Tarjan–van Leeuwen result and why the inverse Ackermann function means “almost constant”.
- Use
- Apply union-find to counting connected components, equivalence classes and Kruskal's algorithm.
16.1Disjoint sets
Who is friends with whom in a social network, which intersections of a city are joined by road, which terminals of a circuit are soldered to the same conductor? In all these questions the items are divided into groups, and each item is in exactly one group. Over time the groups merge: when a road is built between two intersections, two regions become one. Groups are never seen to split. The structure needed for this kind of problem is very simple. It supports just two operations, but it performs them extremely fast. Written in a few lines, this structure shows up as a building block in many graph algorithms. It should be learned well first, so that it comes to mind and can be used when needed.
Before turning to programming, the problem must be stated correctly in the language of mathematics, as someone who does not know programming would state it. A correctly formed definition shows from the start which operations are needed and which are superfluous.
16.1.1Disjoint sets and the forest representation
The items are named by the numbers 0, 1, …, n − 1. These numbers can be a student's ID, a computer's position in a network or the code of an intersection. The actual data of the items is kept in another array; union-find works only with the numbers.
Let the universe be U = {0, 1, …, n − 1}. If the sets S1, S2, …, Sk are subsets of U and Si ∩ Sj = ∅ for every i ≠ j, these sets are called pairwise disjoint sets. For short they are called disjoint sets. A data structure that supports the union and find operations on disjoint sets is called union-find.
The condition in the definition says that no item is in two sets at once. Every item has exactly one set; so the question “which set is the item in?” always has a single answer.
For n = 10, the sets S1 = {0, 6, 7, 8}, S2 = {1, 4, 9} and S3 = {2, 3, 5} are pairwise disjoint. The intersections S1 ∩ S2, S2 ∩ S3 and S1 ∩ S3 are all empty. The union of the three sets gives the whole universe, that is, ten items. All the first examples in this chapter work with these three sets.
How should the sets be represented on a computer? The chosen way is to represent each set as a tree. One of the set's elements becomes the root and the others sit below it. There is one important difference from ordinary trees: the links point from child to parent. Each node knows only its own parent; it does not know its children. That is why the arrows in Figure 16.1 point upward. A collection of mutually disjoint trees is called a forest. The representation of disjoint sets is also a forest.
The placement within the trees has no meaning. That 6, 7 and 8 sit below 0 does not mean that 0 is “special” in this set. The same set could be represented by a tree in which 7 is the root and the others are attached to it. The tree's only job is to carry the information “these items belong together”. This freedom is very useful later: we can choose the shape of the tree as we like, in the direction that lowers the cost.
Why the links point upward also follows from the operations. Union-find never asks “list the elements of this set”. The question is always “which set is this item in?” This question is answered by starting at an item and climbing to the root. To climb, it is enough for each node to know its parent. Keeping child lists would both waste memory and never be used by any operation.
16.1.2Union and find
The structure supports two operations:
- Union of disjoint sets. If Si and Sj are two disjoint sets, their union is the set Si ∪ Sj = {x : x ∈ Si ∨ x ∈ Sj}. After the union, Si and Sj no longer exist separately; a single set takes their place. For example, S1 ∪ S2 = {0, 6, 7, 8, 1, 4, 9}.
- Find.
find2(i)finds the set that contains the element i. The root of the tree is returned as the name of the set.
Union is very easy with trees. One of the roots of the two trees is made a child of the other. A single link is enough for this: the parent information of one of the roots is updated to point to the other root. Figure 16.2 shows two forms of the same union. In the bottom left figure the parent of 4 has been made 0, and the tree of S2 has become a subtree of 0. In the bottom right figure the parent of 0 has been made 4. Both results represent the same set, and both are correct. But the shapes of the trees differ. Which one is chosen determines the cost of later find operations. Most of this chapter is about how to make that choice.
In the form on the right, the distance of items 6, 7 and 8 from the root has grown from 1 to 2. In the form on the left, only the distances of 1, 4 and 9 have grown, each by one. Finding the set of an item means walking from that item to the root. As the distance to the root grows, find becomes more expensive. The weighting rule rests on this small observation.
16.1.3The name of the set: the root
Names like S1, S2 are for humans. Algorithms associate each set name with the root of the tree. Instead of “the set S1” one says “set number 0”. In this way the root number returned by find2 becomes the name of the set.
| Set name | Link (root) |
|---|---|
| S1 | → 0 |
| S2 | → 4 |
| S3 | → 2 |
Using the root as the name has an important consequence. Whether two items are in the same set is decided by comparing their roots. The question find2(8) == find2(6) means “are 8 and 6 in the same set?” Both calls return 0, so the answer is yes. find2(8) == find2(9) compares 0 with 4; the answer is no.
The name of a set can change with a union. After the union on the right of Figure 16.2, the set of 8 is no longer 0 but 4. So the set of an item should not be saved in a variable and used later. Every question is answered by calling find2 again on the current trees.
Taking a root number to be the permanent identity of an item. Writing int k = find2(8); and using k after a few unions can give a wrong result. Since roots change places in a union, 0 may no longer be a root. A root is the name of the set only at the moment it was asked.
16.2Array implementation
The model is ready: each set is a tree, the root of each tree is the name of the set, and the links go from child to parent. Now we must decide how to store this model in C.
16.2.1Implementation options
The first way that comes to mind is to keep each set as a linked list. Joining two lists end to end is done by changing the pointer of the last node; union is O(1). But to find out which list an item is in, the lists have to be scanned from start to end. Find becomes O(n). Keeping the sets in sorted arrays speeds up the search, but every union requires merging or re-sorting two sorted arrays. The cost of that goes up to O(n lg n).
| Method | Union | Find | Problem |
|---|---|---|---|
| Linked list | O(1) | O(n) | Slow search |
| Keep sorted | — | — | Sorting O(n lg n) |
| Parent array (tree) | O(1) | Tree depth | Depth must be kept small |
The third row is the most promising. Union is again just writing a single link. The cost of find, on the other hand, equals the depth of the tree. If the depth can be kept small, find becomes fast as well.
Trees are usually built from node structures and pointers. That is not needed here. The items are already numbered from 0 to n − 1; the number can be used directly as an array index. Each node needs only a single piece of information: the number of its parent. So the whole forest fits into a single integer array of n elements. It is possible to implement it with the array, the most reliable, robust and fastest data structure. Access to an item in an array is O(1), no pointer chasing is needed, malloc is called just once, and since memory is contiguous the cache is also used well.
16.2.2The parent array
A parent array is an int array of n elements. parent[i] is the number of the parent of node i in the tree, that is, of the node one level above it. If i is a root, parent[i] holds a negative value. In the first version this value is −1.
The node immediately above a node is its parent; the parent array in the code holds these parent links. Since a root has no parent, no valid index can be written into its cell. Because node numbers are 0 or positive, a negative value cannot be confused with any node and is safely used as the “this is a root” mark. Figure 16.3 shows the parent array of the example forest.
parent[i] is the parent of i; roots hold −1.The array is easy to read. The parent of 1 and 9 is 4; parent[1] and parent[9] contain 4. The parent of 3 and 5 is 2. The parent of 6, 7 and 8 is 0. 0, 2 and 4 are the roots of the sets: parent[0] = parent[2] = parent[4] = −1. In C this array is defined as follows:
#define N 10
int parent[N] = { -1, 4, -1, 2, -1, 2, 0, 0, 0, 4 };In memory this array is 10 consecutive int cells. On a 64-bit Windows or Linux machine an int is 4 bytes and the array takes 40 bytes. If the array starts at address 0x1000, the cell parent[i] is at address 0x1000 + 4i. Table 16.3 gives this view. In a tree with pointers each node would be a separate malloc block and carry at least one pointer (8 bytes). Here 4 bytes per node are enough and all the trees sit in a single block.
| Address | 0x1000 | 0x1004 | 0x1008 | 0x100C | 0x1010 | 0x1014 | 0x1018 | 0x101C | 0x1020 | 0x1024 |
|---|---|---|---|---|---|---|---|---|---|---|
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| Value | −1 | 4 | −1 | 2 | −1 | 2 | 0 | 0 | 0 | 4 |
The parent array defines a tree completely by itself. Given the array, the tree can be drawn: for each i it is enough to draw an arrow from i to parent[i]. The reverse is also true: every tree gives a single parent array. However, the array does not say directly what the children of a node are. To find the children of 0, one must scan the whole array and collect the cells whose value is 0. Since union-find never asks this question, this shortcoming is not a problem.
16.2.3Building the parent array in dynamic memory
The code in the slides defines the parent array as a global array of size #define N 10. This keeps the routines short and is enough for examples. In a real program, however, the number of items is usually known only at run time: the number of vertices of a graph read from a file is not known at compile time. In that case the array is allocated with malloc. The following code gathers the number of items and the array into a single structure:
typedef struct {
int n; /* number of items */
int *parent; /* parent[i]: parent of i; at a root, -(number of nodes) */
} sets;
sets *sets_create(int n) {
sets *k = malloc(sizeof *k);
if (k == NULL) return NULL; /* out of memory */
k->parent = malloc(n * sizeof *k->parent);
if (k->parent == NULL) { /* array could not be allocated */
free(k); /* give back the half-built structure */
return NULL;
}
k->n = n;
for (int i = 0; i < n; i++)
k->parent[i] = -1; /* every item is a singleton set */
return k;
}
void sets_free(sets **sp) {
if (*sp == NULL) return;
free((*sp)->parent); /* inner array first */
free(*sp); /* then the structure itself */
*sp = NULL; /* the caller's pointer becomes empty */
}sets_create allocates two separate blocks. The first is the structure itself: an int and a pointer. On a 64-bit machine sizeof(sets) is 16 bytes: 4 bytes for n, 4 bytes of alignment padding and 8 bytes for the pointer. The second block is the parent array of n integers. In the expression malloc(n * sizeof *k->parent), sizeof *k->parent gives the size of the array's element type. Even if the type is later changed to long, this line does not have to change.
After every malloc call a NULL check is made. If the first block cannot be allocated, there is nothing to do; the routine returns NULL. If the second block cannot be allocated, the situation is subtler. At this point there is a block that was allocated for the structure. If the routine simply returned NULL, that block would be in nobody's hands and could never be given back. This is a memory leak. That is why the code first frees the half-built structure with free(k) and then returns NULL. The last loop makes every item a singleton set: at the start all cells are −1.
sets_free gives the blocks back in the reverse of the order they were allocated. First the inner array, then the structure is released. If the order were reversed, that is, if free(*sp) were called first, the expression (*sp)->parent would read a block that had been given back. This is undefined behavior. The routine takes a pointer to pointer as its parameter: sets **sp. That way it can write NULL into the caller's own variable in the last line. After the caller says sets_free(&k), k is NULL. If sets_free(&k) is called a second time by mistake, nothing happens because of the check in the first line. If the parameter were just sets *k, the routine could set its own copy to NULL, while the caller's k would keep pointing to the block that had been given back. Such a pointer is called a dangling pointer.
These two routines were tried with a counting malloc/free wrapper: at the end of creation and deletion, 2 allocations and 2 frees were counted, and no leak was seen. In the rest of the chapter, to stay consistent with the slides, the routines use the global parent array. To move to the dynamic structure, a parameter sets *k is added to each routine and k->parent[i] is written in place of parent[i]; the logic does not change at all.
16.2.4The first version: find1 and union1
The first version is the most direct C translation of the model:
int find1(int i) {
for (; parent[i] >= 0; i = parent[i])
; /* climb until negative */
return i;
}
void union1(int i, int j) {
parent[i] = j; /* hook set i under j */
}find1 is a single for loop. The initialization part of the loop is empty, because the starting node is already the parameter i. The condition parent[i] >= 0 says “i is not a root”. While the condition is true, i = parent[i] climbs to the next node up. The body of the loop is empty; the lone semicolon shows this. All the work is done in the condition and update parts. The loop stops at the first node whose parent value is negative, that is, at the root. The routine returns this root.
A loop with an empty body is a common idiom in C, but it is not easy to read. Writing the semicolon on a separate line with a comment next to it is a deliberate choice. Had the semicolon been written right at the end of the for line, a reader might have taken it for a typo.
union1 is a single assignment: parent[i] = j. The parent of the root i is now j; the whole tree of i goes under j. The routine has a precondition: i and j must be the roots of different sets. If an item that is not a root is given, its root is first found with find1. If the precondition is violated, either a tree is split in two or a root points to itself and the find routine falls into an infinite loop.
The costs are clear. union1 makes a single assignment: Θ(1). find1(i) runs the loop once for each edge on the path from i to the root. If the distance of i from the root is d, it makes d hops and d + 1 comparisons: Θ(d + 1). In this chapter a “hop” means one execution of the assignment i = parent[i]. In the worst case d is the distance of the deepest node of the tree from the root. The extra memory of both routines is O(1): only the variable i is used.
16.2.5Code trace
In the example forest, let find1(9), union1(4, 0) and again find1(9) be called in this order. Table 16.4 gives the state of i and of the array at each step. Figure 16.4 draws three important moments.
| Step | Operation | i | Check | Result |
|---|---|---|---|---|
| 1 | find1(9) | 9 | parent[9] = 4 ≥ 0 | i = 4 |
| 2 | 4 | parent[4] = −1 < 0 | Root; return 4 | |
| 3 | union1(4, 0) | — | — | parent[4] = 0 |
| 4 | find1(9) | 9 | parent[9] = 4 ≥ 0 | i = 4 |
| 5 | 4 | parent[4] = 0 ≥ 0 | i = 0 | |
| 6 | 0 | parent[0] = −1 < 0 | Root; return 0 |
find1(9) stops at 4. Middle: union1(4, 0) changes a single cell: parent[4] = 0. Bottom: the second find1(9) walks one hop further and stops at 0.The first call reaches 4 with a single hop: 9 is in set number 4. The union changes just one cell. But this single assignment increases by one the distance to the root of every node below 4. The second find call therefore makes two hops and returns 0: now 9 is in set number 0. The cost of find equals the depth of the node searched for. Union is cheap, but its price shows up in later find operations.
The values in the table were verified with a driver compiled together with the code in the slides: the first call returned 4 and the second returned 0. In the same driver the comparison find1(8) == find1(6) also gave 1 (true).
16.3Analysis of the first version
It is not enough for an algorithm to be correct. It must be efficient and written according to the rules of software engineering. Even these are not enough: one must ask which data will stress the algorithm the most. Whatever happens in the background, what is the longest the code can run? Asking and answering this question is what separates someone who knows a programming language from a computer engineer. If an employer says “you all know C, so you all get the same salary”, the engineer's answer is ready: give a problem, and look at how it is solved and how long the solution takes in the worst case.
16.3.1A bad sequence of operations
Let us start with n singleton sets: Si = {i}, with parent[i] = −1 for every i. Then let the following sequence of operations be applied:
/* start with n singleton sets */
union1(0, 1);
union1(1, 2);
...
union1(n-2, n-1);
find1(0);
find1(1);
...
find1(n-1);Each union attaches the root of the tree built in the previous step under a new singleton set. union1(0, 1) puts 0 under 1. union1(1, 2) puts 1, and with it the tree made of 0 and 1, under 2. Both parameters of every union really are roots; the precondition is not violated. But the tree grows by one level at every step. Figure 16.5 shows the result for n = 5.
union1 calls the tree is a chain (left): parent = [1, 2, 3, 4, −1]. On the right, find1(0) has made its fourth hop and reached the root.Each of the unions takes constant time. The problem appears in the find operations. Table 16.5 gives, for each call from find1(0) to find1(4) on the chain, how many hops it makes.
| Call | Level of the node | Path followed | Hops |
|---|---|---|---|
find1(0) | 5 | 0 → 1 → 2 → 3 → 4 | 4 |
find1(1) | 4 | 1 → 2 → 3 → 4 | 3 |
find1(2) | 3 | 2 → 3 → 4 | 2 |
find1(3) | 2 | 3 → 4 | 1 |
find1(4) | 1 | 4 | 0 |
| Total | 10 = 5 · 4 / 2 | ||
16.3.2Total cost
The pattern in the table is the same for every n. In the chain, node i is at level (n − i). It is n − 1 − i edges away from the root.
Apply the calls union1(i, i+1) for i = 0, 1, …, n − 2 in this order to n singleton sets. Then call find1 once for each item. The total number of hops is n(n − 1)/2. The cost of this sequence of operations is Θ(n²).
Each of the n − 1 unions makes one assignment; their total is Θ(n). After the unions, parent[i] = i + 1 (i < n − 1) and parent[n−1] = −1. So find1(i) passes through the nodes i, i + 1, …, n − 1 and makes n − 1 − i hops. The total is Σi=0n−1 (n − 1 − i) = (n − 1) + (n − 2) + … + 1 + 0 = n(n − 1)/2. The total cost is Θ(n) + Θ(n²) = Θ(n²). ∎
A single find1 takes O(n) in the worst case; n of them climb to O(n²) in total. This is unacceptable in problems with millions of items where union-find is used. The measurement in Table 16.6 makes the growth concrete. When n doubles, the number of hops and the time grow about fourfold; this is the sign of quadratic growth.
| n | Hops (first version) | n(n − 1)/2 | Time | Hops (weighted) |
|---|---|---|---|---|
| 1.000 | 499.500 | 499.500 | ≈ 0,001 s | 999 |
| 10.000 | 49.995.000 | 49.995.000 | ≈ 0,13 s | 9.999 |
| 20.000 | 199.990.000 | 199.990.000 | ≈ 0,5–0,6 s | 19.999 |
| 40.000 | 799.980.000 | 799.980.000 | ≈ 2,0–2,7 s | 39.999 |
This sequence of operations spoils the structure of the tree. But the union operation itself is not the culprit. The real problem is which tree is attached under which in the union. At every step the large tree (the chain) was attached under the small single-node tree. Had the order been reversed, that is, had each new node been attached to the root of the large tree, the tree would always have stayed two levels deep. The last column of the table shows this: when the same union requests are made with the weighting rule, the tree stays at two levels and the total of n finds is only n − 1 hops. The weighting rule rests exactly on this idea.
16.3.3Testing the worst case
In worst-case analysis, the code must be tested with the data on which it will crash or run the longest. These data are hard to identify. The sequence of unions that produces a chain is exactly such an input for find1. Random tests easily miss it. When the roots of two randomly chosen items are united, the trees do not grow long like chains. In the measurement, 200,000 random operations were performed on n = 100,000 items; each operation made two finds, and half of the operations included a union. The first version made an average of 1.108 hops per find, and the deepest node was at level 10,130. This is a bad result, but it is still very far from the n levels of a chain. Someone who tests a program only with random data may never see the real worst case.
What the software world calls a “beta version” is an open admission of this difficulty. The producer tells the user: there may be errors we overlooked; if you find any, report them so we can fix them. Software testing is a field in its own right, and many papers have been written about it. The lesson of this chapter is simpler: when a routine is written, one must think of the input that will stress it most and test it with that input as well.
16.4The weighting rule
16.4.1The rule
In a union, the root of one tree goes under the other. The distance to the root of every node of the tree that goes under increases by 1. The nodes of the other tree stay where they are. To keep the cost low, the number of nodes whose distance increases should be small. So the tree with fewer nodes should be attached under the tree with more nodes.
Weighting rule: when performing union(i, j), if the tree of i has fewer nodes than the tree of j, then j is made the parent of i; otherwise i is made the parent of j. In short, the root with more nodes becomes the parent. This rule is also called union by size.
Figure 16.6 shows the effect of the rule. A tree with five nodes rooted at 0 and a tree with two nodes rooted at 5 are merged. In the union on the left, the small tree goes under the large one; only the distance of 5 and 6 from the root grows, and the tree stays at 3 levels. In the union on the right, the large tree goes under the small one; the distance of five nodes grows at once, and the tree climbs to 4 levels.
To apply the rule, the number of nodes of each tree must be known. Should a separate array be kept for that? There is no need. For all nodes other than the root, the parent array holds 0 or positive values. Roots, on the other hand, hold a negative value just to say “I am a root”, and the magnitude of that value has so far never been used. So the number of nodes of a root can be stored in the parent array with a negative sign. At the root, −(number of nodes) is written instead of −1. The sign carries the “root” information and the absolute value the “size” information.
16.4.2union2: minus the node count at the root
void union2(int i, int j) {
/* weighting rule; i and j must be roots */
int p = parent[i] + parent[j]; /* -(total nodes) */
if (parent[i] > parent[j]) { /* i has fewer nodes */
parent[i] = j; /* hook i under j */
parent[j] = p; /* update j's count */
} else { /* j has fewer or equal */
parent[j] = i;
parent[i] = p;
}
}The routine works line by line as follows:
- Line 3.
p = parent[i] + parent[j]. The values at the two roots are negative node counts. Their sum is the negative of the node count of the merged tree. For a tree with 3 nodes and a tree with 5 nodes, p = −3 + (−5) = −8. - Line 4. The comparison
parent[i] > parent[j]looks backward at first glance. Because the values are negative, the larger value indicates the smaller size: −2 > −4 says that 2 nodes are fewer than 4 nodes. If the condition is true, the tree of i has fewer nodes. - Lines 5–6. Since i is smaller, it is hooked under j:
parent[i] = j. The new root is j, and the merged node count is written into its cell:parent[j] = p. - Lines 7–10. Otherwise, that is, if j has fewer or an equal number of nodes, j goes under i and the cell of i becomes p. In case of a tie, attaching j is an arbitrary choice; both choices satisfy the rule.
The order of the assignments matters. If one of the two cells were changed before p is computed in line 3, the node count information would be lost. For example, if parent[i] = j were written first, parent[i] would no longer hold the node count of i but the number of j. That is why the routine takes the sum into a local variable at the very beginning.
The cost is still Θ(1): one addition, one comparison and two assignments. No extra array is needed; the node counts are stored in what was an unused information field. That all cells start at −1 also fits the new meaning: a singleton set has one node.
find1 stays unchanged. All it cares about is whether the value is negative; it makes no distinction between −1 and −8. This is a nice consequence of the choice of representation: the extra information stored at the root does not affect the find routine at all.
16.4.3Code trace
Let us start with eight singleton sets. First, adjacent pairs are united: union2(0, 1), (2, 3), (4, 5), (6, 7). Then the two-node trees two by two: (0, 2), (4, 6). Finally the two four-node trees: (0, 4). In every union the two trees are of equal size. Table 16.7 gives the values at each step.
| Call | parent[i], parent[j] | p | parent afterwards | Level |
|---|---|---|---|---|
(0, 1) | −1, −1 | −2 | [−2, 0, −1, −1, −1, −1, −1, −1] | 2 |
(2, 3) | −1, −1 | −2 | [−2, 0, −2, 2, −1, −1, −1, −1] | 2 |
(4, 5) | −1, −1 | −2 | [−2, 0, −2, 2, −2, 4, −1, −1] | 2 |
(6, 7) | −1, −1 | −2 | [−2, 0, −2, 2, −2, 4, −2, 6] | 2 |
(0, 2) | −2, −2 | −4 | [−4, 0, 0, 2, −2, 4, −2, 6] | 3 |
(4, 6) | −2, −2 | −4 | [−4, 0, 0, 2, −4, 4, 4, 6] | 3 |
(0, 4) | −4, −4 | −8 | [−8, 0, 0, 2, 0, 4, 4, 6] | 4 |
union2(4, 6). Bottom: a single tree after union2(0, 4): 8 nodes, 4 levels, −8 at the root.In every row the condition is false, because the values at the two roots are equal: none of the expressions −1 > −1, −2 > −2 and −4 > −4 is true. So every time the else branch runs and j goes under i. The number of levels grows only when two trees of equal size are united: 2, 3 and 4. The tree with eight nodes has 4 levels. This is exactly the bound given by Theorem 16.2: ⌊lg 8⌋ + 1 = 4.
In the final state the deepest node is 7: the path 7 → 6 → 4 → 0 takes three hops. All the arrays in the table are identical to the output of the driver compiled with the union2 code in the slides.
16.4.4The depth lemma
How badly can the weighting rule distort the tree? The sequence of operations in the trace is the worst case for this rule: every time two trees of equal size are united. In each union the depth of all nodes of the small tree grows by 1, but the tree grows at least twofold. The second observation bounds the first.
Let T be a tree with m nodes obtained by starting from single-node trees and using only union2. The number of levels of T cannot exceed ⌊lg m⌋ + 1.
We prove a stronger statement: every tree with d levels has at least 2d−1 nodes. The proof is by induction on the number of unions performed.
If no union has been performed, the tree has a single node: d = 1 and 1 ≥ 20. Now suppose that two trees with node counts ma ≥ mb and level counts da, db satisfy the statement. union2 attaches the tree b to the root of a (in a tie, too, one of the trees is attached; the naming is chosen accordingly). The number of levels of the new tree is d = max(da, db + 1) and its number of nodes is m = ma + mb. There are two cases:
- If d = da, then m ≥ ma ≥ 2da−1 = 2d−1.
- If d = db + 1, then m = ma + mb ≥ 2mb ≥ 2 · 2db−1 = 2d−1.
In both cases the statement is preserved. Hence m ≥ 2d−1, that is, d − 1 ≤ lg m. Since d − 1 is an integer, we get d − 1 ≤ ⌊lg m⌋ and d ≤ ⌊lg m⌋ + 1. ∎
The essence of the proof is this. The depth of a node grows by 1 only when its tree is attached to a tree that is smaller or equal. At that moment the tree containing the node grows at least twofold. With m nodes, the size can double at most lg m times. So the depth of no node can grow by more than lg m.
The bound is tight, that is, nothing better can be said. A tree built from equal pairs reaches it exactly for every m = 2k. In the measurement, 5 levels were obtained with 16 nodes and 21 levels with 220 = 1,048,576 nodes; both equal ⌊lg m⌋ + 1. With random unions the trees stay far below the bound: with 106 items the bound is 20, while the deepest node was at level 9.
The result is a big gain. The worst-case cost of a single find dropped from O(n) to O(lg n). With a million items this means at most 19 hops instead of a million. The total cost of a sequence of n − 1 unions and m finds is O(n + m lg n). In a mathematics course the question would continue here with “prove that”. For an engineer, what matters is that the complexity dropped from n to ⌊lg n⌋ + 1. This is what improving an algorithm means. But we do not stop here; one more step can be taken.
Reading the comparison of negative values backward. If if (parent[i] < parent[j]) is written, the condition means “i has more nodes”, and the large tree is attached under the small one. The code compiles, the sets stay correct and the results are right; only the trees turn into chains and the cost silently returns to O(n). Mistakes of this kind are noticed only with a worst-case input or by measuring the tree depth.
16.4.5Uniting any two items
union1 and union2 require roots. In practice, requests come such as “put 3 and 8 into the same set”, and 3 and 8 may not be roots. A small wrapper routine can fill this gap:
int unite(int x, int y) { /* x and y are any two items */
int a = find2(x); /* root of x */
int b = find2(y); /* root of y */
if (a == b) return 0; /* already in the same set */
union2(a, b); /* unite the two roots */
return 1;
}The routine first finds the roots of the two items. If the roots are the same, the items are already in the same set and nothing is done; the return value is 0. If they differ, the two roots are given to union2 and 1 is returned. The return value answers the caller's question “did this request perform a new union?” This information is used directly in counting components and in Kruskal's algorithm. The find2 used in the routine is the version of find that applies the collapsing rule (Definition 16.4); find1 can be used in its place as well. The cost equals the cost of two finds; the contribution of the union is constant.
The “are the roots the same?” check is a safety measure. If union1(r, r) is called with the same root, parent[r] = r results: the root points to itself. Every find1 that follows loops forever at this node, because the condition parent[r] ≥ 0 is never false. In the experiment the loop was cut off after a million steps. union2(r, r) breaks in a different way: p = 2 · parent[r] is computed, the condition comes out false, first parent[r] = r and then parent[r] = p are written. In the end the root remains a root, but its node count appears to have doubled. In a three-item experiment the array after union2(1, 1) was [−1, −2, −1]: a singleton set is believed to have 2 items. This wrong count misleads the weighting rule in later unions.
16.5The collapsing rule
16.5.1The rule
In the eight-node tree built with the weighting rule (the lower part of Figure 16.7), find2(7) reaches the root in three hops. If the program calls find2(7) again and again, every call walks the same three steps anew and the cost multiplies. Attaching the tree with fewer nodes to the one with more nodes bounds the depth by lg n, but it does not completely prevent the depth from growing. Since we can no longer check the depth at union time, another opportunity is sought: a find operation walks the whole path anyway. While walking, it can shorten the path.
Collapsing rule: during find2(i), if i is not a root, every node j on the path from i to the root is attached directly to the root. The general name of this idea is path compression.
find2(7), every node on the path 7 → 6 → 4 → 0 will be attached directly to 0.The rule takes advantage of the “meaningless” placement in trees. The position of an item in the tree carries no information; all that matters is which root it reaches. Whether 7 sits under 6 or directly under 0 does not change the sets. What changes is only the cost of later finds. In graph theory the same idea goes by the name “closure”: an indirect connection is shortened by a direct edge. Although the problems are different, the underlying structure is the same, and this similarity is often useful in graph problems.
16.5.2find2
int find2(int i) {
int r, s;
for (r = i; parent[r] >= 0; r = parent[r])
; /* find the root */
while (i != r) { /* collapse the path */
s = parent[i]; /* save i's parent */
parent[i] = r; /* hook i directly to the root */
i = s; /* move on to its parent */
}
return r;
}The routine passes over the path twice.
- First pass (lines 2–4). The
forloop does whatfind1does, but it walks with a separate variablerwithout changingi. When the loop ends,ris the root.istill refers to the starting node; the second pass will start from there. - Second pass (lines 5–9). The
whileloop walks again fromiup to the root. Three things are done in each round. First,s = parent[i]saves the old parent ofi. Thenparent[i] = rattachesidirectly to the root. Finallyi = smoves on to the saved parent. The loop ends whenireaches the root. - Line 10. The root is returned.
The variable s is the vital part of the routine. The assignment parent[i] = r erases the old parent of i. If the old parent is not saved beforehand, the rest of the path is lost; the loop cannot move on to the next node. This is exactly like having to save the next node when reversing a linked list: before a link is changed, the place that link points to must be kept in a variable.
The second loop has a small flaw. It also runs once for a node that is already attached directly to the root and, with the assignment parent[i] = r, rewrites the same value into the cell. This is unnecessary but harmless. Since the last node of the path is always attached to the root, exactly one “extra round” is made in every call except for the root itself.
Cost analysis: if the distance of the starting node from the root is d, the first loop runs d times and the second loop also d times. The cost of a single call is Θ(d + 1); that is, about twice that of find1 alone. Together with the weighting rule, d ≤ ⌊lg n⌋, so a single call is O(lg n) in the worst case. The gain is seen not in a single call but in the sequence of calls: all the nodes on the path are now one hop from the root. The extra memory is O(1): r and s.
The negative number at the root is not disturbed by path compression. Only the cells of nodes other than the root change, and the root's cell is never written to. The number of nodes in the tree does not change either, because no node leaves the tree. The weighting rule therefore works smoothly together with path compression.
16.5.3Code trace
Let us start with the tree at the end of the weighted trace: parent = [−8, 0, 0, 2, 0, 4, 4, 6]. Let find2(7), then again find2(7) and find2(5) be called in this order. Table 16.8 gives the first call step by step.
| Step | Loop | State | Operation | Changed cell |
|---|---|---|---|---|
| 1 | for | r = 7 | parent[7] = 6 ≥ 0 → r = 6 | — |
| 2 | for | r = 6 | parent[6] = 4 ≥ 0 → r = 4 | — |
| 3 | for | r = 4 | parent[4] = 0 ≥ 0 → r = 0 | — |
| 4 | for | r = 0 | parent[0] = −8 < 0: root | — |
| 5 | while | i = 7 | s = 6, parent[7] = 0, i = 6 | parent[7]: 6 → 0 |
| 6 | while | i = 6 | s = 4, parent[6] = 0, i = 4 | parent[6]: 4 → 0 |
| 7 | while | i = 4 | s = 0, parent[4] = 0, i = 0 | (already 0: extra round) |
| 8 | — | i == r | return 0 | parent = [−8, 0, 0, 2, 0, 4, 0, 0] |
r = 0 has been found, and the tree has not changed yet. Middle: find2(7) is finished: 7 and 6 are attached directly to the root. Bottom: after find2(5): 5 is attached to the root too; in the tree only 3 remains under 2.The second call find2(7) is short. Since parent[7] = 0, the first loop finds the root in a single hop. The second loop also runs one round; this round is again an “extra” round, because 7 is already attached to the root. The array does not change.
find2(5), on the other hand, opens up a new path: 5 → 4 → 0. The first loop makes two hops. The second loop attaches 5 to the root (parent[5]: 4 → 0), then runs an extra round for 4. The final state is parent = [−8, 0, 0, 2, 0, 0, 0, 0]. Six of the eight nodes are now attached directly to the root; only 3 is two hops away. All the arrays were compared with the output of the driver compiled with the code in the slides.
Attaching without saving the parent in the while loop: parent[i] = r; i = parent[i];. The second assignment now reads r; i jumps straight to the root and the rest of the path is left uncompressed. Since the routine returns the right root, the error does not show in the output; only the expected speedup does not come. The correct way is to take the old parent into s first.
16.5.4How is this an improvement?
At first glance the objection is fair: there was one for loop, and a while loop has been added. How can this be an improvement? The answer is seen by looking not at a single call but at a sequence of calls. When find2(7) is called a second time, and on every later call, it finds the root in one stroke. Table 16.9 compares the cost of the two versions on the same tree.
| Call | find1 (hops) | find2 (hops + linking) |
|---|---|---|
1st find2(7) | 3 | 3 + 3 |
2nd find2(7) | 3 | 1 + 1 |
10 times find2(7) | 30 | 6 + 9 · 2 = 24 |
find2(5) (afterwards) | 2 | 2 + 2, then 1 + 1 |
The first call is about twice as expensive: 6 steps instead of 3. The second call takes 2 steps instead of 3. Over ten calls the total is 24 against 30, and the difference grows with the number of calls. In a thousand calls find1 makes 3,000 hops, while find2 stays at 6 + 999 · 2 = 2,004 steps. The price of shortening the path is paid once, and its return is collected on every later call.
This kind of calculation is called amortized analysis. Instead of the worst-case cost of a single operation, the total cost of a long sequence of operations is divided by the number of operations. Expensive operations happen once in a while and make the operations that follow them cheaper. When the cost is spread over many operations, it drops to nearly constant per operation.
The effect of path compression is seen most clearly on the worst tree of the weighting rule. On the tree with 220 nodes built from equal pairs (21 levels), 220 random finds were made. With the weighting rule alone an average of 10.00 hops per find was measured; since the tree does not change, this number never decreases. With path compression it dropped to an average of 1.78 hops, and the number of levels of the tree fell from 21 to 6. The time also fell from 0.18 seconds to 0.03 seconds (varies by machine).
16.5.5Recursive path compression
Path compression can also be written in a single line with recursion:
int find(int i) { return parent[i] < 0 ? i : (parent[i] = find(parent[i])); }It reads as follows. If i is a root (parent[i] < 0), it is returned itself. Otherwise the root of its parent is first found recursively: find(parent[i]). The returned root is written into parent[i] and the same value is returned. The value of an assignment expression is the assigned value; so (parent[i] = find(parent[i])) both updates the link and yields the root.
Recursion compresses the path from the root backward. The calls descend to the root, and on the way back each frame attaches its own node to the root. On the eight-node example tree, find(7) calls find(6), which calls find(4), which calls find(0). find(0) returns 0. On the way back parent[4] = 0, parent[6] = 0 and parent[7] = 0 are written in turn. The result is the same as with find2(7): [−8, 0, 0, 2, 0, 4, 0, 0]. After that, find(5) gives [−8, 0, 0, 2, 0, 0, 0, 0], which is also the same.
The difference between the two versions concerns memory. The looping find2 uses O(1) extra memory. The recursive find opens as many call frames as the length of the path: O(d). With the weighting rule d ≤ lg n, so this is not a problem; even with a billion items at most 30 frames are opened. But in a chain built with unweighted union, d can reach n and the call stack can overflow.
16.6The Tarjan–van Leeuwen result and the Ackermann function
16.6.1Almost constant cost
What is the cost when the two rules are used together? The weighting rule bounds a single find by O(lg n). The collapsing rule, since it shortens paths, makes repeated finds cheaper. It is not easy to compute exactly the combined effect of the two. The question was closed by R. E. Tarjan and J. van Leeuwen in 1984.
Start with n singleton sets. Let f finds and u unions be performed in any mixed order, using the weighting rule and the collapsing rule. Let the maximum time required be T(f, u). For u ≥ n/2 there are positive constants k1 and k2 such that
k1 · (n + f · α(f + n, n)) ≤ T(f, u) ≤ k2 · (n + f · α(f + n, n))
holds. Here α is the inverse Ackermann function.
The theorem says two things. The upper bound shows that the total cost of the operations is proportional to n + f · α. The lower bound says that nothing better than this is possible with these two rules; the analysis is tight. The proof of the theorem is beyond the scope of this chapter. But to interpret the result it is enough to know how slowly α grows. α grows so slowly that its value does not exceed 4 even for as many items as there are atoms in the universe. When the total cost is divided by the number of operations, the cost per operation comes out as nearly O(1).
Consider a million items. One program finds the set of an item in nearly constant time, while another still scans lists one by one. Both give the correct result, but one finishes in a small fraction of a second and the other runs for minutes. This is also the difference between a mathematician and an engineer facing the same job: besides the correct result, the engineer also asks about the cost.
16.6.2The Ackermann function
To understand α, one must first look at the function of which it is the inverse. The Ackermann function is a recursively defined function of two natural-number arguments that grows extremely fast.
The Ackermann function is defined for m, n ≥ 0 as follows:
/* Ackermann: grows very fast */
A(m, n) = n + 1 m = 0
= A(m-1, 1) m > 0, n = 0
= A(m-1, A(m, n-1)) m > 0, n > 0The definition has three cases. If m = 0, the result is n + 1; the recursion ends here. If n = 0, the first argument decreases by one and the second argument becomes 1. The third case is the most interesting: the second argument of the outer call is the result of an inner call. The inner call is A(m, n − 1) and the outer call is A(m − 1, …). At every step either m shrinks, or m stays the same and n shrinks. So the recursion always terminates; but when it terminates is another question.
| n = 0 | n = 1 | n = 2 | n = 3 | n = 4 | |
|---|---|---|---|---|---|
| m = 0 | 1 | 2 | 3 | 4 | 5 |
| m = 1 | 2 | 3 | 4 | 5 | 6 |
| m = 2 | 3 | 5 | 7 | 9 | 11 |
| m = 3 | 5 | 13 | 29 | 61 | 125 |
| m = 4 | 13 | 65533 | 265536 − 3 | … | … |
Each row is an iteration of the previous one, and so has a closed form. A(1, n) = n + 2, A(2, n) = 2n + 3 and A(3, n) = 2n+3 − 3. In the row m = 3 the values grow exponentially. In the row m = 4 a tower of exponents begins: A(4, 1) = 216 − 3 = 65533, A(4, 2) = 265536 − 3. The second is a number with about 19,729 digits. A(5, 1) is 3 less than a tower of exponents made of 65536 twos; it is a number of unimaginable size.
The Ackermann function has more than one definition. With the definition above, A(3, 4) = 125. In the definition used in Horowitz's book, which comes from Tarjan's work, one starts with A(1, j) = 2j and gets A(3, 1) = 16. Whichever definition is chosen, the conclusion does not change: all of them grow equally fast, and in practice α ≤ 4.
16.6.3The inverse Ackermann function
The inverse Ackermann function is defined for m ≥ n ≥ 1 as
α(m, n) = min{ i ≥ 1 : A(i, ⌊m/n⌋) ≥ lg n }
That is, α is the smallest first argument for which the Ackermann function exceeds lg n.
Because A grows so fast, the i needed to push it above a given value is very small. So α grows very slowly. Let us do the computation. Since m ≥ n, ⌊m/n⌋ ≥ 1 and A(i, ⌊m/n⌋) ≥ A(i, 1). From the table, A(1, 1) = 3, A(2, 1) = 5, A(3, 1) = 13 and A(4, 1) = 65533. Therefore:
- For n ≤ 23 = 8, lg n ≤ 3 and α ≤ 1.
- For n ≤ 25 = 32, α ≤ 2.
- For n ≤ 213 = 8192, α ≤ 3.
- For n ≤ 265533, α ≤ 4.
The number of atoms in the observable universe is estimated at about 1080, roughly 2266. 265533 is unimaginably larger than that. For every n that can occur on computers, α ≤ 4. Values computed from the definition with a Python script confirmed these thresholds: 1 at n = 8, 2 at n = 9 and 32, 3 at n = 33 and 8192, and 4 at n = 8193, 106 and 264.
Theoretically α grows without bound; so O(α) is not constant, and saying “union-find operations are O(1)” is not strictly correct. In practice, however, α is a factor of at most 4. The right statement is “almost constant” or “a total cost that is linear in practice”.
16.6.4Recursive Ackermann and the call stack
The Ackermann function is a favorite exam question for showing the power of recursion and the limits of the call stack. The question is: write the function recursively; then show the call stack of the call A(1, 2) step by step. The C version is a direct translation of the definition:
unsigned long ackermann(unsigned long m,
unsigned long n) {
if (m == 0) return n + 1;
if (n == 0) return ackermann(m - 1, 1);
return ackermann(m - 1, ackermann(m, n - 1));
}The three cases of the definition correspond to three lines. Since the results grow quickly, unsigned long was chosen as the type; no negative value ever arises. On Windows unsigned long is 32 bits, on Linux 64 bits. A(4, 1) = 65533 fits in both types; A(4, 2), however, fits in no integer type.
The expansion of A(1, 2) is as follows:
A(1,2) = A(0, A(1,1)) = A(0, A(0, A(1,0))) = A(0, A(0, A(0,1))) = A(0, A(0, 2)) = A(0, 3) = 4
| Step | Active calls | Event |
|---|---|---|
| 1 | A(1,2) | Third case: the inner call A(1,1) is needed first. |
| 2 | A(1,2) A(1,1) | Third case again: A(1,0) first. |
| 3 | A(1,2) A(1,1) A(1,0) | n = 0: A(0,1) is called. |
| 4 | A(1,2) A(1,1) A(1,0) A(0,1) | m = 0: returns 2. A(1,0) = 2. |
| 5 | A(1,2) A(1,1) A(0,2) | The inner call gave 2, the outer call is A(0,2): returns 3. A(1,1) = 3. |
| 6 | A(1,2) A(0,3) | The inner call gave 3, the outer call is A(0,3): returns 4. |
| 7 | — | A(1,2) = 4. |
ackermann(1, 2). Top: the stack at its deepest: four active calls, the innermost A(0,1) returning 2. Bottom: the last outer call A(0,3) returning 4.A measurement with an instrumented version showed that A(1, 2) makes 6 calls in total and that the stack grows to at most 4 frames. This agrees with the six distinct calls in the table (A(1,2), A(1,1), A(1,0), A(0,1), A(0,2), A(0,3)). The numbers grow quickly: A(2, 2) takes 27 calls and depth 8, A(3, 3) takes 2,432 calls and depth 63, and A(4, 0) takes 107 calls and depth 16. By a calculation in Python with the same counting rule, A(4, 1) takes 2,862,984,010 calls and the stack reaches a depth of 65,536 frames. Such a depth can easily exceed the default call stack. A(4, 2), on the other hand, finishes on no computer; even the digits of the result do not fit in memory.
16.6.5Comparison by measurement
Three versions were compared on the same random sequence of operations. In each operation the roots of two random items were found; in half of the operations, if the roots differed, the two sets were united. Table 16.12 gives the results.
| Version | n | Hops per find | Deepest level | Time |
|---|---|---|---|---|
union1 + find1 | 100.000 | 1.108,25 | 10.130 | ≈ 2,7–3,1 s |
union2 + find1 | 100.000 | 0,90 | 8 | ≈ 0,007 s |
union2 + find2 | 100.000 | 0,61 | 4 | ≈ 0,006 s |
union2 + find1 | 1.000.000 | 0,91 | 10 | ≈ 0,13 s |
union2 + find2 | 1.000.000 | 0,61 | 5 | ≈ 0,11 s |
On random operations even the first version does not reach the n levels of a chain, but it exceeds a thousand hops per find. The weighting rule reduces this by more than a factor of a thousand. Since weighted trees are already shallow on random input, the contribution of path compression is small here: hops drop from 0.90 to 0.61. When the linking rounds are counted too, the total work increases slightly (about 360 thousand against 492 thousand steps on 100,000 items), while the time stays about the same. The real value of path compression is seen in bad cases where the same deep paths are walked again and again. The measurement on the tree built from equal pairs showed this: 10.00 hops per find dropped to 1.78.
16.6.6Where do these results come from?
Tarjan is a famous computer scientist who is the author of many fundamental results on graph algorithms. This theorem comes from his joint work with J. van Leeuwen (1984). Results of this kind are the product of research. In undergraduate education one studies for four years and gains a profession. In a doctorate, one often works for four years on a single problem and looks for an answer to a question that has not yet been solved anywhere in the world. Such work is carried out not alone but within a group; a person working in a group keeps learning.
One should not expect these topics to be finished in a week; if one does not work at all, they never get finished. Studying two or three hours regularly every day and reviewing the topic of the week within the same week keeps the topics from piling up. A short but deep structure like union-find is best learned during this review by tracing small examples by hand.
16.7Applications
16.7.1Counting connected components
The largest groups of vertices that can reach one another by some path in an undirected graph are called connected components. Components partition the vertex set into disjoint parts; so this is a natural application of union-find. At the start every vertex is a separate component. Every edge unites the components in which its two endpoints lie. When all edges have been processed, the number of remaining sets is the number of components.
int components(int n, int m, int u[], int v[]) {
for (int i = 0; i < n; i++) parent[i] = -1;
int count = n; /* every vertex separate */
for (int e = 0; e < m; e++) {
int a = find2(u[e]), b = find2(v[e]);
if (a != b) { /* different component */
union2(a, b);
count--;
}
}
return count;
}The routine takes a graph with n vertices and m edges as two arrays: the e-th edge connects the vertices u[e] and v[e]. The first line builds the parent array from scratch; every vertex is a singleton set. The variable count holds the number of components and starts at n. For each edge the loop finds the roots of the two endpoints. If the roots differ, the edge unites two separate components: the roots are united with union2 and the component count decreases by one. If the roots are the same, the two endpoints of the edge are already in the same component; the edge closes a cycle and the count does not change.
The example graph has 6 vertices and 4 edges: (0, 1), (2, 3), (1, 4) and (3, 2). The last edge is a second edge between 2 and 3. Table 16.13 gives the trace.
| Edge | a | b | Decision | parent afterwards | count |
|---|---|---|---|---|---|
| (0, 1) | 0 | 1 | Different: union2(0, 1) | [−2, 0, −1, −1, −1, −1] | 5 |
| (2, 3) | 2 | 3 | Different: union2(2, 3) | [−2, 0, −2, 2, −1, −1] | 4 |
| (1, 4) | 0 | 4 | Different: union2(0, 4) | [−3, 0, −2, 2, 0, −1] | 3 |
| (3, 2) | 2 | 2 | Same: closes a cycle | unchanged | 3 |
The third edge has an interesting moment. The edge is (1, 4), but 1 is not a root. find2(1) returns 0, the root of 1, and the union is made between 0 and 4. The tree of 0 has two nodes and that of 4 has one; since −2 > −1 is false, 4 goes under 0. Both endpoints of the fourth edge reach the root 2, and the edge is skipped. The result is 3: {0, 1, 4}, {2, 3}, {5}. The routine was compiled with the code in the slides and run; it returned 3 and the final array was [−3, 0, −2, 2, 0, −1].
Cost: the first loop is Θ(n). The edge loop runs m times; each round makes two finds and at most one union. By Theorem 16.3 the total is O(n + m · α(m + n, n)); in practice this is linear. Memory is the parent array of n integers. The adjacency list of the graph is not built; edges can be processed as they are read. This property makes union-find attractive compared with depth-first search for very large graphs whose edges arrive in sequence from a file or the network.
16.7.2Equivalence classes
A relation is an equivalence relation if it is reflexive (x ≡ x), symmetric (if x ≡ y then y ≡ x) and transitive (if x ≡ y and y ≡ z then x ≡ z). An equivalence relation partitions the items into disjoint sets called equivalence classes. The classic problem in Horowitz's book is this: a series of declarations of the form i ≡ j is given; find the classes. For example, the EQUIVALENCE declarations that tell a compiler which variables share the same memory area are processed in this way.
Because of transitivity, declarations have indirect consequences: if 7 ≡ 4 and 0 ≡ 4, then 7 ≡ 0, even if this is not declared separately. Union-find gathers these indirect consequences automatically. Each declaration unites the sets of two items:
void equivalence(int n, int m, int x[], int y[]) {
for (int i = 0; i < n; i++) parent[i] = -1;
for (int k = 0; k < m; k++)
unite(x[k], y[k]); /* declaration x[k] ≡ y[k] */
for (int r = 0; r < n; r++) { /* every root is a class */
if (parent[r] >= 0) continue;
printf("{");
for (int i = 0; i < n; i++)
if (find2(i) == r) printf(" %d", i);
printf(" }\n");
}
}Let us try it with 12 items and nine declarations: 0 ≡ 4, 3 ≡ 1, 6 ≡ 10, 8 ≡ 9, 7 ≡ 4, 6 ≡ 8, 3 ≡ 5, 2 ≡ 11, 11 ≡ 0. Table 16.14 gives the roots found at each declaration and the classes after the declaration.
| Declaration | Roots | Classes afterwards (those with more than one element) |
|---|---|---|
| 0 ≡ 4 | 0, 4 | {0, 4} |
| 3 ≡ 1 | 3, 1 | {0, 4}, {1, 3} |
| 6 ≡ 10 | 6, 10 | {0, 4}, {1, 3}, {6, 10} |
| 8 ≡ 9 | 8, 9 | {0, 4}, {1, 3}, {6, 10}, {8, 9} |
| 7 ≡ 4 | 7, 0 | {0, 4, 7}, {1, 3}, {6, 10}, {8, 9} |
| 6 ≡ 8 | 6, 8 | {0, 4, 7}, {1, 3}, {6, 8, 9, 10} |
| 3 ≡ 5 | 3, 5 | {0, 4, 7}, {1, 3, 5}, {6, 8, 9, 10} |
| 2 ≡ 11 | 2, 11 | {0, 4, 7}, {1, 3, 5}, {6, 8, 9, 10}, {2, 11} |
| 11 ≡ 0 | 2, 0 | {0, 2, 4, 7, 11}, {1, 3, 5}, {6, 8, 9, 10} |
At the fifth declaration, 4 is no longer a root; its root is 0. At the last declaration, the root of 11 is 2. Since the tree of 2 has two nodes and the tree of 0 has three, −2 > −3 is true and 2 goes under 0. The program prints three classes: { 0 2 4 7 11 }, { 1 3 5 } and { 6 8 9 10 }. This output was obtained with the C driver.
The final loop that prints the classes scans all the items for each root and calls find2 for each item. If the number of classes is k, this part makes O(k · n) finds; if all items are in separate classes, it climbs to O(n²). A better way is to scan the items once and append each to the list of its root: O(n · α). The simple way was chosen to keep the example short. Processing the declarations is O(n + m · α).
16.7.3Kruskal's algorithm
Among the trees that span all the vertices of a connected weighted graph, the one with the smallest sum of edge weights is called the minimum spanning tree. Kruskal's algorithm builds this tree greedily. The edges are sorted by weight from smallest to largest and examined in order. If find2 gives different roots for the endpoints of an edge, the edge is taken into the tree and the two sets are united. If it gives the same root, the edge closes a cycle and is rejected.
The reason for the rejection rule is this. If the two endpoints are already in the same set, there is a path between them made of previously chosen edges. The new edge would close this path into a cycle. Since the tree must not have a cycle, the edge cannot be taken. Union-find answers the question “is there a path of chosen edges between these two endpoints?” in nearly constant time. There is no need to search for a path in the graph.
typedef struct { int u, v, w; } edge; /* endpoints and weight */
static int edge_cmp(const void *a, const void *b) {
const edge *x = a, *y = b;
return (x->w > y->w) - (x->w < y->w); /* smaller weight first */
}
int kruskal(int n, int m, edge e[], edge chosen[]) {
qsort(e, m, sizeof e[0], edge_cmp);
for (int i = 0; i < n; i++) parent[i] = -1;
int k = 0; /* number of chosen edges */
for (int t = 0; t < m && k < n - 1; t++) {
int a = find2(e[t].u), b = find2(e[t].v);
if (a != b) { /* does not close a cycle */
union2(a, b);
chosen[k++] = e[t];
} /* a == b: edge is rejected */
}
return k; /* if n-1, the graph is connected */
}An edge is kept as a structure: two endpoints and a weight. qsort is the sorting routine of the standard library; the comparison function looks at the weights of the two edges. The expression (x->w > y->w) - (x->w < y->w) gives −1, 0 or 1. Writing x->w - y->w would be shorter, but it can cause integer overflow with very large weights. The loop ends early when n − 1 edges have been chosen, because a tree on n vertices has exactly n − 1 edges. The routine returns the number of chosen edges. If this number is less than n − 1, the graph is not connected and the result is a spanning forest, not a spanning tree.
Let the edges of an example graph with 5 vertices be as follows, written as (endpoint, endpoint, weight): (0, 1, 4), (0, 2, 1), (1, 2, 2), (1, 3, 5), (2, 3, 8), (3, 4, 3), (2, 4, 9). After sorting, the weights come in the order 1, 2, 3, 4, 5, 8, 9.
| Edge | Roots | Decision | parent afterwards |
|---|---|---|---|
| (0, 2, 1) | 0, 2 | Taken | [−2, −1, 0, −1, −1] |
| (1, 2, 2) | 1, 0 | Taken | [−3, 0, 0, −1, −1] |
| (3, 4, 3) | 3, 4 | Taken | [−3, 0, 0, −2, 3] |
| (0, 1, 4) | 0, 0 | Rejected: cycle through the path 0–2–1 | unchanged |
| (1, 3, 5) | 0, 3 | Taken | [−5, 0, 0, 0, 3] |
The chosen edges are (0, 2), (1, 2), (3, 4) and (1, 3); the total weight is 1 + 2 + 3 + 5 = 11. The edge (0, 1, 4) is rejected, because the path 0–2–1 between 0 and 1 has already been chosen. The program gave the same four edges and the total 11.
The cost has two parts. Sorting is O(m lg m). The union-find part is at most 2m finds and n − 1 unions: O(m · α). Sorting determines the total: O(m lg m). Without the nearly constant cost of union-find, for example if the first version were used, the loop part would climb to O(m · n) and exceed the sorting.
16.7.4Other areas of use
- Network connectivity. Answering questions like “are these two computers connected?” online, as connections are added. Sedgewick's book introduces union-find with this example.
- Image processing. Splitting neighboring pixels of the same color into regions. This operation is called connected component labeling; each pixel is an item and each adjacency is a union.
- Percolation. Testing whether an open path from top to bottom exists in a grid made of randomly opened cells. The core of Monte Carlo experiments is this question asked after each newly opened cell.
- Compilers. Unification, which equates two type expressions in type inference, and alias analysis, which finds which pointers may point to the same memory.
- Offline lowest common ancestor. Tarjan's algorithm finds the lowest common ancestor (LCA) of node pairs known in advance in a tree, in a single traversal with union-find.
In all these applications the problem is different, but the underlying structure is the same: groups only grow and never split, and one often asks “are they in the same group?” If items must be removed from groups or a group must be split in two, union-find is not suitable; it does not support these operations.
16.8Exam question: the contents of the parent array
Questions of this kind measure not memorizing code but being able to trace it by hand. The question is as follows:
(i) Since union2 is used, the roots hold minus the node count, not −1. This is the trap of the question: a student who writes −1 at the roots in (i) also gets (ii) wrong, because the weight comparisons are made with wrong numbers. S1 has 4 items, S2 has 3 and S3 has 3:
parent = [−4, 4, −3, 2, −3, 2, 0, 0, 0, 4]
(ii) The calls are traced in order.
The result is [4, 4, 4, 4, −10, 4, 0, 4, 0, 4]. All ten items are gathered in one set, with root 4. Only 6 and 8 still reach the root through 0; find has not yet been called for them. All the intermediate arrays were obtained exactly in the driver compiled with the code in the slides.
The note “2 is already attached” in the second step is the extra round of find2. The path is 5 → 2 → 4; the while loop first attaches 5 and then 2 to the root. Since 2 is already attached to 4, the second assignment does not change the value.
16.9Complexity summary
| Version | Union | Find (worst case) | n − 1 unions + m finds |
|---|---|---|---|
union1 + find1 | O(1) | O(n) | O(n + m · n) |
union2 (weighted) | O(1) | O(lg n) | O(n + m lg n) |
union2 + find2 | O(1) | O(lg n) per operation | O(n + m · α(m + n, n)) |
Memory is the same in every version: just the parent array of n integers. Since the weighting rule stores the node count in the negative value at the root, it needs no extra array. Because α ≤ 4, the last row is linear in practice.
The essence of the table can be said in a single sentence: union by itself is always O(1); what determines the cost is the depth of the tree, that is, find. The weighting rule bounds the depth and the collapsing rule shortens the paths. That union is constant is misleading, because union requires roots, and finding a root is a call to find2. In practice a request to “unite two items” therefore costs two finds plus one union.
16.10Common mistakes
- Giving union an arbitrary node instead of a root. In
union1(i, j), if i is not a root, the assignmentparent[i] = jcuts the link between i and its old parent. i and its subtree move to the set of j, while the rest of the old tree stays in the old set. Two sets have not been merged; one has been split. In the example forest,union1(9, 2)moves only 9; 1 and 4 stay in the old set. The fix is to find the roots first withfind. - Uniting two roots in the same set, that is, a root with itself (i == j).
union1(r, r)links the root to itself and later finds fall into an infinite loop.union2(r, r)doubles the node count. The roots must be compared before uniting. - Reading the comparison of negative values backward in the weighting rule. −2 > −4 means “fewer nodes”. A reversed comparison does not break the sets, but it turns the trees into chains, and the error is noticed only by measurement.
- Forgetting to update the node count at the root (
p) in the union. The old count stays at the new root and later comparisons are made with wrong weights. Computingpbefore either of the cells is changed is equally important. - Attaching in
find2without saving the parent intos. The rest of the path is lost; the path stays uncompressed. - Not filling the parent array with −1 at the start. Global arrays start at zero; the contents of an array obtained with
mallocare indeterminate. In an array full of zeros the parent of every node is 0 and the parent of 0 is also 0:findfalls into an infinite loop at 0. - Not checking the return of
mallocand forgettingfree. In the dynamic version, if theparentarray is not given back, the program leaks 4n bytes on every call. Before giving the structure back, the inner array must be given back.
16.11Exercises and solutions
Exercise 1. n = 6, parent all −1. What is parent after the calls union2(0, 1); union2(2, 3); union2(0, 2); union2(4, 5);?
Solution. The first two calls unite equal trees: parent[1] = 0, parent[0] = −2; parent[3] = 2, parent[2] = −2. In the third call both roots hold −2; in a tie, 2 goes under 0 and parent[0] = −4. The fourth call writes parent[5] = 4, parent[4] = −2. The result is [−4, 0, 0, 2, −2, 4]: root 0 has 4 nodes and root 4 has 2 nodes. Verified with the driver.
Exercise 2. With the weighting rule, what is the maximum depth of a tree with 16 nodes?
Solution. By Theorem 16.2, ⌊lg 16⌋ + 1 = 5 levels. The tree that reaches the bound is built from equal pairs: 8 pairs, 4 fours, 2 eights, 1 sixteen. The measurement also gave 5 levels.
Exercise 3. Write a union rule that keeps height instead of weight. What changes?
Solution. −(number of levels) is kept at the root. The lower tree is attached under the higher one; if the heights are equal, one goes under the other and the number of levels increases by 1. This method is called union by rank:
void union3(int i, int j) {
/* height rule; i and j are roots; at a root -(number of levels) */
if (parent[i] > parent[j]) { /* the tree of i is lower */
parent[i] = j;
} else if (parent[i] < parent[j]) { /* the tree of j is lower */
parent[j] = i;
} else { /* equal heights */
parent[j] = i;
parent[i]--; /* number of levels grows by 1 */
}
}The comparison is again between negative values: the larger value points to the lower tree. When two trees of different heights are united, the height does not change, because the lower tree goes under the root of the higher one and reaches at most its height. With the sequence of operations of Exercise 1 the result is [−3, 0, 0, 2, −2, 4]: the same trees, but root 0 holds the number of levels, 3, instead of the node count, 4. With equal pairs of 16 nodes, 5 levels again result. The depth is again bounded by O(lg n); the proof is the same as for the weighting rule (a tree with d levels has at least 2d−1 nodes). When used together with the collapsing rule, path compression lowers the height but the root does not know this; the stored value is no longer the true height but an upper bound on it. That is why it is called “rank” rather than height.
Exercise 4. Write find2 recursively.
Solution. One-line path compression: int find(int i) { return parent[i] < 0 ? i : (parent[i] = find(parent[i])); }. A detailed explanation and a memory comparison are in 16.5.5.
Exercise 5. Why does the rejection of an edge in Kruskal's algorithm mean a cycle?
Solution. An edge is rejected if its endpoints are in the same set. Being in the same set means there is a path of previously chosen edges between the two endpoints, because sets are merged only by chosen edges. The new edge connects the two ends of this path directly and closes the path into a cycle.
Exercise 6. What is the cost of finding the number of components of a graph with n vertices and m edges?
Solution. Building the parent array is O(n); the edge loop is 2m finds and at most n − 1 unions. With the two rules together the total is O(n + m · α(m + n, n)); in practice it is linear.
16.12Summary
- Model. Disjoint sets are represented by trees whose root is the set name and whose links go from child to parent. There are two operations: union and find. Two items are in the same set if their roots are the same.
- Representation. The whole forest sits in a single
intarray:parent[i]is the parent of i; a negative value is found at a root. If the array is built withmalloc,NULLis checked after every allocation and the blocks are given back in reverse order. - First version.
union1is a single assignment;find1walks to the root and takes as long as the depth of the node. - Worst case. Arbitrary linking without a rule can produce a chain: after the sequence
union1(i, i+1), n finds take exactly n(n − 1)/2 hops, that is, Θ(n²). Random tests easily miss this input. - Weighting rule. The small tree is attached under the large one. The node count is stored at the root with a minus sign; no extra array is needed. The depth does not exceed ⌊lg m⌋ + 1, and the bound is reached exactly by equal pairs.
- Collapsing rule. During find, every node on the path is attached directly to the root. The first call is about twice as expensive, but later searches finish in one stroke. The old parent must be saved before linking.
- Result. The two rules together give a cost per operation proportional to α (Tarjan–van Leeuwen). The inverse Ackermann function does not exceed 4 for n ≤ 265533; the cost is almost O(1) in practice.
- Applications. Counting components, equivalence classes and Kruskal's algorithm use the same pattern: find the roots of the two endpoints; if they differ, unite them; if they are the same, there is a cycle.
16.13Key terms
- disjoint sets
- union-find
- union
- find
- forest
- root
- parent
- parent array
- weighting rule
- union by rank
- collapsing rule
- path compression
- worst case
- amortized analysis
- Ackermann function
- inverse Ackermann function
- call stack
- stack overflow
- connected component
- minimum spanning tree
- memory leak
- dangling pointer
- pointer to pointer
16.14Test Yourself
How many sets are there in the array
parent = [−1, 0, 0, 1, 1, −1, 5]? What doesfind1(4)return and how many hops does it make?Answer
There are two cells with negative values (0 and 5); two sets: {0, 1, 2, 3, 4} and {5, 6}.
find1(4)follows the path 4 → 1 → 0 and returns 0 after 2 hops.The calls
union1(i, i+1)for i = 0, …, 6 are applied to n = 8 singleton sets. Then onefind1is called for each item. How many hops are made in total?Answer
n(n − 1)/2 = 8 · 7 / 2 = 28.
find1(0)makes 7 hops,find1(1)6, … andfind1(7)0.With
parent = [−3, 0, 0, −5, 3, 3, 3, 3],union2(0, 3)is called. What does the array become?Answer
p = −8. −3 > −5 is true: the tree of 0 is smaller and goes under 3. The result is
[3, 0, 0, −8, 3, 3, 3, 3].With
parent = [−8, 0, 0, 2, 0, 4, 4, 6],find2(3)is called. How many rounds does each loop run, and what does the array become?Answer
The path is 3 → 2 → 0. The
forloop makes 2 hops and thewhileloop runs 2 rounds: 3 is attached to the root and an extra round is made for 2. The result is[−8, 0, 0, 0, 0, 4, 4, 6], and the return value is 0.In a tree with 1024 nodes built with the weighting rule, how many hops does a single
find1make at most?Answer
The number of levels is at most ⌊lg 1024⌋ + 1 = 11. From the deepest node to the root there are 10 edges: at most 10 hops.
What is α(n, n) for n = 1000? (With the A of the definition.)
Answer
⌊n/n⌋ = 1, lg 1000 ≈ 9.97. A(1, 1) = 3 and A(2, 1) = 5 are not enough; A(3, 1) = 13 ≥ 9.97. The answer is 3.
What does
ackermann(2, 1)return, and how many calls are made in total?Answer
A(2, 1) = 2 · 1 + 3 = 5. In an instrumented run, 14 calls were made.
The edges of a graph with 5 vertices are (0, 1), (1, 2), (2, 0), (3, 4). What does
componentsreturn? Which edge does not change the count?Answer
It returns 2: {0, 1, 2} and {3, 4}. Both endpoints of the edge (2, 0) reach the root 0; the edge closes the cycle 0–1–2 and the count does not change.
What would be lost if
sets_freetook the parameter assets *kinstead ofsets **sp?Answer
The routine could still give the blocks back, but it could not set the caller's pointer to
NULL. The caller's variable would keep pointing at memory that had been given back, that is, it would be a dangling pointer. A second delete call would try to give the same block back twice, and undefined behavior would result.
16.15Further reading
- E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2nd ed., Section 5.10 (Set Representation). The parent array, the weighting rule and the collapsing rule are presented in the same order as in this chapter, with their lemmas.
- T. H. Cormen et al., Introduction to Algorithms, the chapter “Data Structures for Disjoint Sets”. It gives a detailed proof of the bound with α for union by rank and path compression.
- R. Sedgewick, Algorithms in C, Chapter 1. It develops union-find step by step with the network connectivity example and compares the versions with measurements.
- R. E. Tarjan, J. van Leeuwen, “Worst-case analysis of set union algorithms”, Journal of the ACM 31(2), 1984. It is the source of Theorem 16.3; it studies many variants of path compression together.
16.16References
- E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, Section 5.10 (Set Representation).
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms (CLRS), the chapter “Data Structures for Disjoint Sets”.
- R. Sedgewick, Algorithms in C, Chapter 1 (connectivity with union-find).
- R. E. Tarjan, J. van Leeuwen, “Worst-case analysis of set union algorithms”, J. ACM 31(2), 1984.
Related pages: Chapter 16 slides · © Sercan Külcü. All rights reserved.