Disjoint-set data structure

Name

Disjoint sets
Sets
Data structure
Connectivity

Edit

In computing, a disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (nonoverlapping) subsets. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:

Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.

Union: Join two subsets into a single subset.

Because it supports these two operations, a disjoint-set data structure is sometimes called a union-find data structure or merge-find set. The other important operation, MakeSet, which makes a set containing only a given element (a singleton), is generally trivial. With these three operations, many practical partitioning problems can be solved (see the Applications section).

In order to define these operations more precisely, some way of representing the sets is needed. One common approach is to select a fixed element of each set, called its representative, to represent the set as a whole. Then, Find(x) returns the representative of the set that x belongs to, and Union takes two set representatives as its arguments.

Disjoint-set linked lists

A simple approach to creating a disjoint-set data structure is to create a linked list for each set. The element at the head of each list is chosen as its representative.

MakeSet creates a list of one element. Union appends the two lists, a constant-time operation. The drawback of this implementation is that Find requires Ω(n) or linear time to traverse the list backwards from a given element to the head of the list.

This can be avoided by including in each linked list node a pointer to the head of the list; then Find takes constant time, since this pointer refers directly to the set representative. However, Union now has to update each element of the list being appended to make it point to the head of the new combined list, requiring Ω(n) time.

When the length of each list is tracked, the required time can be improved by always appending the smaller list to the longer. Using this weighted-union heuristic, a sequence of m MakeSet, Union, and Find operations on n elements requires O(m + nlog n) time.^[1] For asymptotically faster operations, a different data structure is needed.

Analysis of the naive approach

We now explain the bound $O(n \log(n))$ above.

Suppose you have a collection of lists and each node of each list contains an object, the name of the list to which it belongs, and the number of elements in that list. Also assume that the sum of the number of elements in all lists is $n$ (i.e. there are $n$ elements overall). We wish to be able to merge any two of these lists, and update all of their nodes so that they still contain the name of the list to which they belong. The rule for merging the lists $A$ and $B$ is that if $A$ is larger than $B$ then merge the elements of $B$ into $A$ and update the elements that used to belong to $B$ , and vice versa.

Choose an arbitrary element of list $L$ , say $x$ . We wish to count how many times in the worst case will $x$ need to have the name of the list to which it belongs updated. The element $x$ will only have its name updated when the list it belongs to is merged with another list of the same size or of greater size. Each time that happens, the size of the list to which $x$ belongs at least doubles. So finally, the question is "how many times can a number double before it is the size of $n$ ?" (then the list containing $x$ will contain all $n$ elements). The answer is exactly $\log_2(n)$ . So for any given element of any given list in the structure described, it will need to be updated $\log_2(n)$ times in the worst case. Therefore updating a list of $n$ elements stored in this way takes $O(n \log(n))$ time in the worst case. A find operation can be done in $O(1)$ for this structure because each node contains the name of the list to which it belongs.

A similar argument holds for merging the trees in the data structures discussed below. Additionally, it helps explain the time analysis of some operations in the binomial heap and Fibonacci heap data structures.

C# Other implementations: C++ F# Pascal

public class DisjointSet
{
    private readonly int[] _parent;
    private readonly int[] _rank;
    public int Count { get; private set; }

    public DisjointSet(int count, int initialize = 0)
    {
        Count = count;
        _parent = new int[Count];
        _rank = new int[Count];
        for (var i = 0; i < initialize; i++) _parent[i] = i;
    }

    private DisjointSet(int count, int[] parent, int[] rank)
    {
        Count = count;
        _parent = parent;
        _rank = rank;
    }

    public void Add(int v)
    {
        _parent[v] = v;
        _rank[v] = 0;
    }

    public int Find_Recursive(int v)
    {
        if (_parent[v] == v) return v;
        return _parent[v] = Find(_parent[v]);
    }

    public int Find(int v)
    {
        if (_parent[v] == v) return v;
        var last = v;
        while (_parent[last] != last) last = _parent[last];
        while (_parent[v] != v)
        {
            var t = _parent[v];
            _parent[v] = last;
            v = t;
        }
        return last;
    }

    public int this[int v]
    {
        get { return Find(v); }
        set { Union(v, value); }
    }

    public void Union(int a, int b)
    {
        a = Find(a);
        b = Find(b);
        if (a == b) return;
        if (_rank[a] < _rank[b])
        {
            var t = _rank[a];
            _rank[a] = _rank[b];
            _rank[b] = t;
        }
        _parent[b] = a;
        if (_rank[a] == _rank[b]) _rank[a]++;
    }

    public int GetSetCount()
    {
        var result = 0;
        for (var i = 0; i < Count; i++)
        {
            if (_parent[i] == i) result++;
        }
        return result;
    }

    public DisjointSet Clone()
    {
        var rank = new int[Count];
        _rank.CopyTo(rank, 0);
        var parent = new int[Count];
        _parent.CopyTo(parent, 0);
        return new DisjointSet(Count, parent, rank);
    }

    public override string ToString()
    {
        return string.Join(",", _parent.Take(50));
    }
}