深夜学算法之Union Find Set：动态连通

1. 前言

并查集（Union Find Set），也称为不相交集数据结构（Disjointed Set Data Structure），两个名字各自概括了这一数据结构的部分特征。简单地讲，并查集维护了一列互不相交的集合S1、S2、S3、…，支持查找（find）与合并（union）两种操作。

• find
  找到元素所在的集合，通常返回该集合的代表元（representative）
  元素a与元素b是否属于同一个集合，只要判断find（a）与find（b）是否相等
• union
  将两个集合合并为一个集合
  将元素a与元素b所在的集合合并为一个集合，使用union（a，b）

我的实现在这里

2. 原理

2.1 基础算法

UnionFindSet用树表示集合，所谓维护一列互不相交的集合也就是有许多棵树。每棵树的元素属于一个集合，树根的元素就是集合的代表元，所以UnionFindSet实际上维护了一个多棵树构成的森林。

• find(x)就是找x所在的树的树根
• union(x, y)就是合并x和y所在的树

来看UnionFindSet的定义：

class UnionFindSet {
    public:
        UnionFindSet(int n);
        int Find(int x);
        void Union(int x, int y);
    private:
        std::vector<int> parent;
};

与常见的树形数据结构不同，并查集的链接关系不是从parent指向child而是从child指向parent，这个链接信息保存在parent数组里。

1. 若parent[x] == x，则x就是x所在树的树根
2. 若parent[x] != x，则x是parent[x]的子节点

解释完parent的含义，Find的实现方法也就呼之欲出了。

int UnionFindSet::Find(int x) {
    if (parent[x] == x)
        return x;
    else
        return Find(parent[x]);
}

构造函数UnionFindSet(int n)表示最初有n个互不相交的集合，代表元分别为0、1、2、…(n-1)。

UnionFindSet::UnionFindSet(int n) {
    parent.resize(n);
    for (int i = 0; i < n; ++i) {
        parent[i] = i;
    }
}

要合并两棵树，只要把一棵根节点的parent设为另一棵树的根节点。

void UnionFindSet::Union(int x, int y) {
    int root_x = Find(x);
    int root_y = Find(y);
    if (root_x == root_y)
        return;
    parent[root_y] = root_x;
}

用图形解释find和union中parent的作用，其中child在下层，parent在上层。
3的parent是2，那么调用find(3)时：

• parent[3] = 2，调用find(2)
• parent[2] = 2，返回2

调用find(3)

调用union(1, 3)时：

• 调用find(1)，得到root_x = 0
• 调用find(3)，得到root_y = 2
• parent[2] = 0

调用union(1, 3)

2.2 优化合并

并查集就是一组树构成的森林，与通常的搜索树相比只是链接关系从parent->child变成了child->parent，所以也会出现搜索树中的问题。极端情况下n个节点像链表那样构成n层，对于最底层的节点，find复杂度自然是O(n)，而union由于调用find复杂度也会变成O(n)。
既然树的高度影响效率，那么可以设法避免高树出现，也就是本小节的优化合并；也可以设法把高树变矮，也就是下一小节的路径压缩。

优化合并就是优化union操作，简单粗暴地讲，就是合并时永远把矮树作为高树的子树。判断哪棵树比较矮有union-by-size和union-by-height两种做法，union-by-height是在类中添加height数组记录每个节点的高度，union-by-size是在类中添加size数组记录每个节点的子节点数量，两者效果完全相同。我采用union-by-height，感兴趣union-by-size的可以看这里

在类中添加height数组：

class UnionFindSet {
    public:
        UnionFindSet(int n);
        int Find(int x);
        void Union(int x, int y);
        void Display(void);
    private:
        std::vector<int> parent;
        std::vector<int> height;
};

修改构造函数UnionFindSet(int n)：

UnionFindSet::UnionFindSet(int n) {
    parent.resize(n);
    height.resize(n);

    for (int i = 0; i < n; ++i) {
        parent[i] = i;
        height[i] = 0;
    }
}

新的union算法：

void UnionFindSet::Union(int x, int y) {
    int root_x = Find(x);
    int root_y = Find(y);

    if (root_x == root_y)
        return;

    if (height[root_x] > height[root_y]) {
        parent[root_y] = root_x;
    } else if (height[root_x] < height[root_y]) {
        parent[root_x] = root_y;
    } else {
        parent[root_y] = root_x;
        ++height[root_x];
    }
}

注意只有根节点高度相同时需要更新height，因为两棵树高度不相等时矮的那棵至少比高的矮一层。因此对于有n个节点的并查集，height的最大值为lgn，所以find和union的算法复杂度都至多为O(lgn)。

2.3 路径压缩

路径压缩就是改造find操作，直接来看代码：

int UnionFindSet::Find(int x) {
    if (parent[x] == x)
        return x;
    else {
        int result = Find(parent[x]);
        parent[x] = result;
        return result;
    }
}

也就是说在查找时，把查找路径上节点的parent都设为根节点，从而把这棵树「压平」，加速以后的查找。用图形演示find(4)就是：

调用find(4)前 调用find(4)后

这时find操作也会改变树高，所以height数组里的值就不是准确的树高，而是估计树高（estimated height），或者称为秩（rank），这时做法也成为union-by-rank。

3. 应用

并查集可以用于检测无向图中是否存在环。假设无向图中有v个节点和e条边，用伪代码形式写就是：

bool detect_cycle(v, e) {
    u = UnionFindSet(v)
    for (int i = 0; i < e.size; ++i) {      
  
        (p, q) = e(i); // 取得第i条边的两个节点

        if (u.find(p) == u.find(q))
            return true;
        u.union(p, q);
    }
    return false;
}

所以可以把并查集用在kruskal最小生成树算法里，实现可以参考这里

注意与BFS/DFS相比，并查集检测速度快，但只能检测环的存在，不能确定哪些节点构成了环。

4. 参考资料

• Disjoint-set data structure（Wiki）：
  https://en.wikipedia.org/wiki/Disjoint-set_data_structure
• Disjoint-set data structure（Mathblog）：
  http://www.mathblog.dk/disjoint-set-data-structure/

5. 附录：关于代表元

下图是一张典型的无向图，有a、b、c、d、e五个节点：

一张典型的无向图

记** S(x) **表示包含节点x的极大连通子图里节点的集合，显然有：

S(a) = S(b)= S(c) = { a，b，c }
S(d) = S(e) = { d，e }

不同的集合有 {a，b，c} 和 {d，e} 两个，而且它们互不相交。代表元是一个集合里的典型元素，可以从集合里任意选取，比如 {a，b，c} 的代表元可以用a，也可以用b或c。由于集合互不相交，所以代表元互不相同，判断「两个元素是否属于同一个集合」等价于判断「两个元素所在集合的代表元是否相等」。

**find(x) **就是找到元素x所在集合的代表元。
分别取a、d为两个集合的代表元，那么有：

find(a) = find(b) = find(c) = a
find(d) = find(e) = d

b和e不在同一个集合里，相应的有find（b）不等于find（e）。

现在我们在原图里添加一条连接b和d的边：

添加边后

发生了什么事情？图上两个互相不连通的部分结合了，这时应该有：

S(a) = S(b)= S(c) = S(d) = S(e) = { a，b，c，d，e }

**union(x, y) **就是将元素x和元素y所在的集合合并成一个集合。
union(b, d)之后，b所在的、以a为代表元的集合，与d所在的、以d为代表元的集合合成了一个大的新集合，将这个新集合代表元取为a，则有：

find(a) = find(b) = find(c) = find(d) = find(e) = a

b和e现在在同一个集合里，所以有find（b）等于find（e）。