数据结构与算法(34): 不相交集（并查集）

发表于   |   分类于

介绍

  不相交集（Disjoint-set）也称并查集（Union-find set），对于n个不同且不相交元素， 不相交集为支持以下两种操作的数据结构。

  • 找出给定元素所属的集合
  • 合并两个集合

操作

不相交集的操作：

  • MAKE-SET(x)：建立一个有唯一元素x的集合，并且x不在其他集合中。
  • UNION(x,y)：合并x和y所在的集合，x和y所在的原集合都不再存在，产生一个合并后的新集合。

    合并两个不相交集合比较简单的方法就是，找到其中一个集合根节点，将另外一个集合的根节点指向它。

  • FIND-SET(x)：返回包含x的集合。

    查找集合时，一般采用递归查找得到集合的根节点。

优化

路径压缩

  FIND-SET(x)：采用递归查找时，整棵树可能变为一条链，这时每次查找都是$O(n)$的复杂度。
  为了避免这种情况，需要对路径进行压缩，即当经过“递归”找到祖先节点后，在“回溯”的时候顺便将它的子孙节点直接指向祖先，这样以后每次查找操作的复杂度都变成了$O(1)$。

合并优化

  合并的时候将元素少的集合合并到元素多的集合中，这样合并之后树的高度会相对较小。

  • 按大小合并
    使得较小的树成为较大的树的子树。
  • 按高度合并
    使得较浅的树成为较深的树的子树。
  • 按秩合并
    路径压缩不完全与按高度求并兼容，因为路径压缩可以改变树的高度。按秩合并就是对每棵树存储的高度是其估计高度（称为秩），也就是按高度合并的时候不去重新计算树的高度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
 * 不相交集
 * 路径压缩和按秩合并：m次union/find操作复杂度最坏为：O(mlog(n))
 */
public class DisjointSet {
    private int[] s;
    public DisjointSet(int size) {
        s = new int[size];
        // 初始化，让每个根的数组元素存储它的树的秩的负值(这样就不需要额外的存储空间来存储秩rank)
        for (int i = 0; i < size; i++){
            s[i] = -1;
        }
    }
    /**
     * 使用路径压缩进行查找优化
     * @param x
     * @return
     */
    public int find(int x){
        if (s[x] < 0){
            return x;
        }else {
            return s[x] = find(s[x]);
        }
    }
    /**
     * 按秩合并
     * @param x
     * @param y
     */
    public void union(int x, int y){
        int root1 = find(x);
        int root2 = find(y);
        if (root1 != root2){
            if (s[root1] < s[root2]){
                // root1的秩大, 将秩小的树合并到秩大的树的子树中
                s[root2] = root1;
            }else {
                if (s[root1] == s[root2]){
                    // 两个数的秩一样时,增加合并后的树的秩
                    s[root2]--;
                }
                s[root1] = root2;
            }
        }
    }
    public void print(){
        for (int i: s){
            System.out.print(i + " ");
        }
    }
}