In computer science, a disjoint-set data structure is a data structure that assigns each element in a set to one of a number of disjoint (nonoverlapping) groups of elements. A union-find algorithm is a way of performing two critical operations on such a data structure:
- Find: Determine which group a particular element is in.
- Union: Combine two groups into a single group.
The other important operation, Make-Set, which makes a singleton set containing only a given element, is generally trivial. With these three operations, many practical partitioning problems can be solved (see the Applications section).
While we could represent the sets themselves as objects and have the operations operate on these sets, the more common approach is to choose an element from each set as a representative; then, Find returns the representative of the set that the given element is in, and Union takes the representatives of two given sets.
Disjoint-set linked lists
Perhaps the simplest approach to creating a disjoint-set data structure is to create a linked list for each group. We choose the element at the head of the list as the representative.
Make-Set is obvious, creating a list of one element. Union simply appends the two lists, a constant-time operation. Unfortunately, it seems that Find requires O(n) or linear time with this approach.
We can avoid this by including in each linked list node a pointer to the head of the list; then Find takes constant time. However, we've now ruined the time of Union, which has to go through the elements of the list being appended to make them point to the head of the new combined list. We can ameliorate this by always appending the smaller list to the longer, but even in this case Union can take Ω(n) time on average. To solve this, we need to start over with a different data structure.
Disjoint-set forests
In a disjoint-set forest, each set is represented by a tree data structure where each node holds a reference to its parent node. The representative of each set is the tree's root. Find-Set simply follows parent nodes until it reaches the root. Union combines two trees into one by making the root one of them the child of the root of the other. In this naive form, this approach is no better than the linked-list approach, because the tree it creates can be highly unbalanced, but it can be enhanced in two ways.
The first way, called union by rank, is to always attach the smaller tree to the root of the larger tree, rather than vice versa. To evaluate which tree is larger, we use a simple heuristic called rank: one-element trees have a rank of zero, and whenever two trees of the same rank are unioned together, the result has one greater rank. Just applying this technique alone yields an average running-time of O(log n) per Make-Set, Union, or Find operation.
The second way, called path compression, is a way of flattening the structure of the tree whenever we use Find on it. The idea is that each node we visit on our way to a root node may as well be attached directly to the root node; they all share the same representative. To effect this, we make one traversal up to the root node, to find out what it is, and then make another traversal, making this root node the immediate parent of all nodes along the path. The resulting tree is much flatter, speeding up future operations.
These two techniques complement each other; applied together, the average time per operation is only O(α(n)), where α(n) is the inverse of the function f(n) = A(n,n), where A is the extremely quickly-growing Ackermann function. Since α(n) is its inverse, it's less than 5 for all remotely practical values of n, and so is effectively a small constant.
Applications
Disjoint-set data structures arise naturally in many applications, particularly where some kind of partitioning or equivalence relation is involved, and this section discusses some of them.
Finding the connected components of an undirected graph
Initially, we assume that every vertex in the graph is in its own connected component, and is not connected to any other vertex. To represent this, we use Make-Set to initially make a set for each vertex containing only that vertex.
Next, we simply visit each vertex and use Union to union its set with the sets of all its neighbors. Once this is done, we will have one group for each connected component, and can use Find to
Computing shorelines of a terrain
When computing the contours of a 3D surface, one of the first steps is to compute the "shorelines," which surround local minima or "lake bottoms." We imagine we are sweeping a plane, which we refer to as the "water level," from below the surface upwards. We will form a series of contour lines as we move upwards, categorized by which local minima they contain. In the end, we will have a single contour containing all local minima.
Whenever the water level rises just above a new local minimum, it creates a small "lake," a new contour line that surrounds the local minimum; this is done with the Make-Set operation.
As the water level continues to rise, it may touch a saddle point, or "pass." When we reach such a pass, we follow the steepest downhill route from it on each side until we arrive a local minimum. We use Find to determine which contours surround these two local minima, then use Union to combine them. Eventually, all contours will be combined into one, and we are done.
References
- Chapter 21, Introduction to Algorithms, 2nd ed. Cormen, Leiserson, Rivest, Stein. ISBN 0262032937.