Union-Find并查集详解

Union find(并查集)是Disjoint set data type(不相交集合数据结构)的一种。

首先简介一下Disjoint set data type(不相交集合数据结构)。 set的实质是将集合中的元素按照某种规则进行划分到不相交的子集中去，如果两个元素属于同一个集合，则我们可以抽象认为它们“等价”。又由于集合之间的“不相交”的性质，因此，任何两个元素x、y之间的关系有且仅有两种：等价或者不等价（即x和y要么属于同一个集合，要么属于不同的集合）。又由于任何一个集合的所有元素都是等价的，因此可称每个集合为一个“等价类”。一般来说，我们可以取其中任何一个元素代表这个集合，又称“代表元”。

Disjoint set data type的表示如下：

用tree 来表示每一个等价类，其中root是代表元

在Disjoint set data type 上支持以下两种运算：

• FIND(x) ：返回包含x的集合的代表元(root)
• UNION(x, y)：将包含x的集合与包含y的集合并起来

1. 对于FIND(x)，最简单的实现方法是，从x开始不断的寻找它的parents，直到找到一个元素的parents是它本身，则完成。如下图所示

Find(x) 的实现，O(n)

优化方法是使用Path Compression，不断将“中间路径”的节点直接与代表元连接。

Find(n)的优化，～O(1)

• 2. 对于UNION(x,y)，则需要引入rank的概念。采用Link-by-rank策略：对于每一个tree，使用一个整数rank来标记，起始值为0。连接两个tree时，将rank较小的root连接到rank较大的tree上，再将其rank值增加1。演示如下：

综合以上所述，编写UnionFindSet的C++代码示例如下：

UnionFindSet
{
public:
    UnionFindSet(int n)
    {
        _parents = std::vector<int>(n+1,0);
        _ranks = std::vector<int>(n+1,0);

        for(int i = 0; i < _parents.size(); i++)
            _parents[i] = i;
    }

    //Merge set contains u and v
    //return true if merge seccuessful, false if u and v already in one set
    bool Union(int u, int v)
    {
        int pu = Find(u);
        int pv = Find(v);

        if(pu == pv)
            return false;

        if(_ranks[pu] < _ranks[pv])
            _parents[pu] = pv;
        else if(_ranks[pu] > _ranks[pv])
            _parents[pv] = pu;
        else
        {
            _parents[pu] = pv;
            _ranks[pv] += 1;
        }
        return true;
    }

    //Get the root of u
    int Find(int u)
    {
        //compress the path during traversal
        if(u != _parents[u])
            _parents[u] = Find(_parents[u]);
        return _parents[u];
    }
private:
    std::vector<int> _parents;
    std::vector<int> _ranks;
};

代码清单： https://github.com/ShulinLiu/DataStructure-Algorithm/blob/master/BasicDataStructure/UnionFindSet.hpp