Union

S₁ ∪ S₂ = {1, 7, 8, 9, 2, 5, 10}

To perform the union, make one of the trees a subtree of the other.

To obtain the union of two sets, set the parent field of one of the roots to the other root.

Data representation for S₁, S₂ and S₃

To determine which set an element is currently in, follow the parent links to the root of its tree and use the pointer to the set name.

Represent set elements 1 to n by using an array p[1:n]. The i^th element of this array represents the tree node that contains element i. A root stores −1.

Array representation for S₁, S₂, S₃.

Find(i)

Find(i) is implemented by following the indices, starting at i, until we reach a node with parent value −1.

Simple algorithms

Algorithm SimpleUnion(i, j)
{
    p[i] := j;
}

Algorithm SimpleFind(i)
{
    while (p[i] ≥ 0) do i := p[i];
    return i;
}

Trace: In Fig (b), after SimpleUnion(1, 5), perform Find(9).

Performance of SimpleUnion and SimpleFind

The performance of SimpleUnion and SimpleFind is not very good.

Example: If q elements are in a set S_i = {i}, 1 ≤ i ≤ q, then the initial configuration consists of a forest with q nodes, each a root with p[i] = −1.

Let the sequence of operations performed on the sets be:

Union(1, 2), Union(2, 3), Union(3, 4), Union(4, 5), …, Union(n−1, n), Find(1), Find(2), …, Find(n)

This sequence results in a degenerate tree.

• The time taken by Union is constant, so n−1 unions take $O\left(n\right)$.
• Find requires following a sequence of parent pointers from the element to be found to the root.
• Since the time required to process a find for an element at level i of a tree is $O\left(i\right)$, the total time needed to process the n finds is:

Weighting rule for Union(i, j)

This time complexity can be improved by avoiding the creation of degenerate trees. To accomplish this, use the weighting rule for Union(i, j).

Weighting rule: If the number of nodes in the tree with root i is less than the number in the tree with root j, then make j the parent of i; otherwise make i the parent of j.

Trees obtained using the weighting rule

To implement the weighting rule, we maintain a count field in the root of every tree. If i is a root node, then count[i] is the number of nodes in the tree. The array stores p[i] = −count[i] for a root.

Algorithm WeightedUnion(i, j)

Algorithm WeightedUnion(i, j)
/* Union sets with roots i and j, i ≠ j, using the weighting rule.
   p[i] = -count[i] and p[j] = -count[j]. */
{
    temp := p[i] + p[j];
    if (p[i] > p[j]) then
    {   // i has fewer nodes
        p[i] := j;  p[j] := temp;
    }
    else
    {   // j has fewer or equal nodes
        p[j] := i;  p[i] := temp;
    }
}

Time complexity of WeightedUnion is $O\left(1\right)$.

The height of each tree with m nodes is:

Example

n = 8 and p[i] = −count[i] = −1, 1 ≤ i ≤ 8. Let S₁ = {1}, S₂ = {2}, …, S₈ = {8}. The sequence is:

Union(1, 2), Union(3, 4), Union(5, 6), Union(7, 8), Union(1, 3), Union(5, 7), Union(1, 5)

• Now the time to process a find is $O\left(\log m\right)$ if there are m elements in a tree.
• If an intermixed sequence of u union and f find operations is to be processed, it takes:

WeightedUnion(i, j) trace

Collapsing rule

Collapsing rule: If j is a node on the path from i to its root and p[j] ≠ root[i], then set p[j] to root[i].

Algorithm CollapsingFind(i)
/* Find the root of the tree containing element i.
   Use the collapsing rule to collapse all nodes from i to the root. */
{
    r := i;
    while (p[r] > 0) do r := p[r];     // find the root
    while (i ≠ r) do
    {
        s := p[i]; p[i] := r; i := s;
    }
    return r;
}

SimpleFind and CollapsingFind compared

Follow the example above to process Find(8), Find(8), …, Find(8): eight find operations on element 8.

• In SimpleFind, Find(8) requires going up three parent link fields, for a total of 24 moves to process all 8 finds.
• In CollapsingFind, the first Find(8) goes up three links to find the root and three more to collapse the path. Each of the remaining seven finds requires going up only one link field. The total cost is now only 13 moves.

CollapsingFind(i) trace for i = 8

Starting array: p = [−8, 1, 1, 3, 1, 5, 5, 7].

Resulting array:

Application: connected components

To use union-find to find the connected components of a graph, we can perform the following steps:

1. Initialize each vertex as a separate component.
2. For each edge in the graph, perform a union operation on the two components that the edge connects.
3. After all edges have been processed, the connected components of the graph will be the disjoint sets in the union-find data structure.

Assume the graph is undirected always, if not specified as directed.

Implementation

Let S = {S₁, S₂, …, S_n}.

• MAKE-SET(x): S_i = {x}, add S_i to S.
• UNION(x, y): x ∈ S_x and y ∈ S_y, then $$S=S-S_x-S_y\cup \{S_x\cup S_y\}$$
• FIND-SET(x): returns the representative of the set that contains x.

Algorithm

CONNECTED_COMPONENTS(G)
    for each vertex v ∈ G.V
        MAKE-SET(v)
    for each (u, v) ∈ G.E
        if FIND-SET(u) ≠ FIND-SET(v)
            UNION(u, v)

Trace

Two connected components exist in the given graph: (1) {a, b, c, d, e, f, g} and (2) {h, i, j}.