Disjoint-set data structure

Disjoint-set/Union-find Forest
Type	multiway tree
Invented	1964
Invented by	Bernard A. Galler and Michael J. Fischer
Time complexity in big O notation Operation Average Worst case Search O(α(n)) O(α(n)) Merge O(α(n)) O(α(n)) Space complexity Space O(n) O(n)

MakeSet creates 8 singletons.

After some operations of Union, some sets are grouped together.

In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It provides near-constant-time operations (bounded by the inverse Ackermann function) to add new sets, to merge existing sets, and to determine whether elements are in the same set. In addition to many other uses (see the Applications section), disjoint-sets play a key role in Kruskal's algorithm for finding the minimum spanning tree of a graph.

History

Disjoint-set forests were first described by Bernard A. Galler and Michael J. Fischer in 1964. In 1973, their time complexity was bounded to $\Omega (log^{*}(n))$, the iterated logarithm of $n$, by Hopcroft and Ullman. (A proof is available here.) In 1975, Robert Tarjan was the first to prove the $O(\alpha (n))$ (inverse Ackermann function) upper bound on the algorithm's time complexity, and, in 1979, showed that this was the lower bound for a restricted case. In 1989, Fredman and Saks showed that $\Omega (\alpha (n))$ (amortized) words must be accessed by any disjoint-set data structure per operation, the optimality, thereby proving the optimality of the data structure.

In 1991, Galil and Italiano published a survey of data strutures for disjoint-sets.

In 1994, Richard J. Anderson and Heather Woll described a parallelized version of Union–Find that never needs to block.

In 2007, Sylvain Conchon and Jean-Christophe Filliâtre developed a persistent version of the disjoint-set forest data structure, allowing previous versions of the structure to be efficiently retained, and formalized its correctness using the proof assistant Coq. However, the implementation is only asymptotic if used ephemerally or if the same version of the structure is repeatedly used with limited backtracking.

Representation

A disjoint-set forest consists of a number of elements each of which stores an id, a parent pointer, and, in efficient algorithms, a value called the "rank".

The parent pointers of elements are arranged to form one or more trees, each representing a set. If an element's parent pointer points to no other element, then the element is the root of a tree and the representative member of its set. A set may consist of only a single element. However, if the element has a parent, the element is part of whatever set is identified by following the chain of parents upwards until a representative element (one without a parent) is reached at the root of the tree.

Forests can be represented compactly in memory as arrays in which parents are indicated by their array index.

Operations

MakeSet

The MakeSet operation makes a new set by creating a new element with a unique id, a rank of 0, and a parent pointer to itself. The parent pointer to itself indicates that the element is the representative member of its own set.

The MakeSet operation has O(1) time complexity.

Pseudocode:

 function MakeSet(x)
   if x is not already present:
     add x to the disjoint-set tree
     x.parent := x
     x.rank   := 0

Find

Find(x) follows the chain of parent pointers from x upwards through the tree until an element is reached whose parent is itself. This element is the root of the tree and the representative member of the set to which x belongs, and may be x itself.

Path compression, is a way of flattening the structure of the tree whenever Find is used on it. Since each element visited on the way to a root is part of the same set, all of these visited elements can be reattached directly to the root. The resulting tree is much flatter, speeding up future operations not only on these elements, but also on those referencing them.

Pseudocode:

 function Find(x)
   if x.parent != x
     x.parent := Find(x.parent)
   return x.parent

Tarjan and Van Leeuwen also developed one-pass Find algorithms that are more efficient in practice while retaining the same worst-case complexity.

Union

Union(x,y) uses Find to determine the roots of the trees x and y belong to. If the roots are distinct, the trees are combined by attaching the root of one to the root of the other. If this is done naively, such as by always making x a child of y, the height of the trees can grow as $O(n)$. To prevent this union by rank is used.

Union by rank always attaches the shorter tree to the root of the taller tree. Thus, the resulting tree is no taller than the originals unless they were of equal height, in which case the resulting tree is taller by one node.

To implement union by rank, each element is associated with a rank. Initially a set has one element and a rank of zero. If two sets are unioned and have the same rank, the resulting set's rank is one larger; otherwise, if two sets are unioned and have different ranks, the resulting set's rank is the larger of the two. Ranks are used instead of height or depth because path compression will change the trees' heights over time.

Pseudocode:

 function Union(x, y)
   xRoot := Find(x)
   yRoot := Find(y)
 
   // x and y are already in the same set
   if xRoot == yRoot            
       return
   
   // x and y are not in same set, so we merge them
   if xRoot.rank < yRoot.rank
     xRoot.parent := yRoot
   else if xRoot.rank > yRoot.rank
     yRoot.parent := xRoot
   else
     //Arbitrarily make one root the new parent
     yRoot.parent := xRoot    
     xRoot.rank   := xRoot.rank + 1

Time Complexity

There are four scenarios to consider, namely implementations which use: path compression, union by rank, both, or neither.

If neither heuristic is used, the height of trees can grow unchecked as $O(n)$, which implies that Find and Union operations will take $O(n)$ time.

Using path compression alone gives a worst-case running time of $\Theta (n+f\cdot (1+log_{2+f/n}n))$, for a sequence of $n$ MakeSet operations (and hence at most $n-1$ Union operations) and $f$ Find operations.

Using union by rank alone gives a running-time of $O(m\log _{2}n)$ (tight bound) for $m$ operations of any sort of which $n$ are MakeSet operations.

Using both path compression and union by rank ensures that the amortized time per operation is only $O(\alpha (n))$, which is optimal, where $\alpha (n)$ is the inverse Ackermann function. This function has a value $\alpha (n)<5$ for any value of $n$ that can be written in this physical universe, so the disjoint-set operations take place in essentially constant time.

Applications

A demo for Union-Find when using Kruskal's algorithm to find minimum spanning tree.

Disjoint-set data structures model the partitioning of a set, for example to keep track of the connected components of an undirected graph. This model can then be used to determine whether two vertices belong to the same component, or whether adding an edge between them would result in a cycle. The Union–Find algorithm is used in high-performance implementations of unification.

This data structure is used by the Boost Graph Library to implement its Incremental Connected Components functionality. It is also a key component in implementing Kruskal's algorithm to find the minimum spanning tree of a graph.

Note that the implementation as disjoint-set forests doesn't allow the deletion of edges, even without path compression or the rank heuristic.

Sharir and Agarwal report connections between the worst-case behavior of disjoint-sets and the length of Davenport–Schinzel sequences, a combinatorial structure from computational geometry.

See also

• Partition refinement, a different data structure for maintaining disjoint sets, with updates that split sets apart rather than merging them together
• Dynamic connectivity

External links

• C++ implementation, part of the Boost C++ libraries
• A Java implementation with an application to color image segmentation, Statistical Region Merging (SRM), IEEE Trans. Pattern Anal. Mach. Intell. 26(11): 1452–1458 (2004)
• Java applet: A Graphical Union–Find Implementation, by Rory L. P. McGuire
• Python implementation
• Visual explanation and C# code