并查集(Union Find)

Posted on | Post modified: | In

并查集的定义

  一种不一样的树形结构，其子节点指向父节点(树通常是父节点指向子节点)。
  对于一组数据，主要支持两个动作:
  union(p,q) 合并p和q两组数据及其集合
  isConnected(p,q) 查询p和q两组数据是否属于同一集合

并查集的应用: 连接问题(Connectivity Problem)

  连接问题和路径问题: 存在路径/不存在 = 连接/不连接
  但，连接问题比路径问题要回答的内容少，连接回答是否连接，而路径问题需要完整路径

经典问题之一：“网络”中节点间的连接状态

经典问题之二：数学中集合类的实现(求并集)

代码实现(Java)

  👇先定义接口，然后使用不同底层数据结构来实现并查集

1
2
3
4
5
public interface UF {
    int getSize();
    boolean isConnected(int p, int q);  // id为p，id为q的两组数据
    void unionElements(int p, int q);
}

Union Find I - Quick Find

  使用一个id数组来存储不同数据所在的集合id
  查找O(1)，合并O(n)

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
public class UnionFind1 implements UF {

    private int[] id;   // id数组

    public UnionFind1(int size) {
        id = new int[size];
        for (int i = 0 ; i < size ; i++) {
            id[i] = i;
        }
    }

    @Override
    public int getSize() {
        return id.length;
    }

    // 查看元素p和q是否同属一个集合
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    // 合并元素p和q的集合
    @Override
    public void unionElements(int p, int q) {
        int pID = find(p);
        int qID = find(q);
        if (pID == qID) return;
        for (int i = 0 ; i < id.length ; i++) {
            if (id[i] == pID) {
                id[i] = qID;
            }
        }
    }

    // 查找元素p所对应的集合编号
    private int find(int p) {
        if (p < 0 || p >= id.length) throw new IllegalArgumentException("out of bound");
        return id[p];
    }
}

Union Find II - Quick Union

  将每一个元素，看做是一个节点，用数组实现子节点指向父节点的思想
  parent数组代表每个元素的父节点(最终形成的是个森林)
  查找O(h)，合并O(h)，h是对应元素所在树的深度，通常比数据总量n要小，但没有具体的log关系，因为树的分支是不确定的

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
public class UnionFind2 implements UF {

    private int[] parent;   // parent数组

    public UnionFind1(int size) {
        parent = new int[size];
        for (int i = 0 ; i < size ; i++) {
            parent[i] = i;
        }
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    // 查看元素p和q是否同属一个集合
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    // 合并元素p和q的集合，O(h)
    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) return;
        parent[pRoot] = qRoot;
    }

    // 查找元素p所对应的集合编号，O(h)
    private int find(int p) {
        if (p < 0 || p >= id.length) throw new IllegalArgumentException("out of bound");
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }
}

Union Find III - 基于size的优化

  在UnionFindII中，合并元素时可能会导致树退化成链表，性能无法保证
  因此，为了防止此类情况，合并时采取将节点数量少的树的根节点指向节点数量多的树的根节点

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
public class UnionFind3 implements UF {

    private int[] parent;   // parent数组
    private int[] sz;       // sz[i]表示以i为根的集合中元素个数

    public UnionFind3(int size) {
        parent = new int[size];
        sz = new int[size];
        for (int i = 0 ; i < size ; i++) {
            parent[i] = i;
            sz[i] = 1;
        }
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    // 查看元素p和q是否同属一个集合
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    // 合并元素p和q的集合，O(h)
    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) return;

        // 根据两个元素所在树的元素个数不同判断合并的方向
        // 将元素少的集合合并到元素多的集合
        if (sz[pRoot] < sz[qRoot]) {
            parent[pRoot] = qRoot;
            sz[qRoot] += sz[pRoot];
        }
        else {
            parent[qRoot] = pRoot;
            sz[pRoot] += sz[qRoot];
        }
    }

    // 查找元素p所对应的集合编号，O(h)
    private int find(int p) {
        if (p < 0 || p >= id.length) throw new IllegalArgumentException("out of bound");
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }
}

Union Find IV - 基于rank的优化

  在UnionFindIII中，合并元素时虽然已经大大改善了链表情况，但是仍存在节点数量少的集合树却有着较高的深度
  因此需要引入基于rank(树的深度/高度)的优化，合并时将深度低的指向深度高的

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
public class UnionFind4 implements UF {

    private int[] parent;   // parent数组
    private int[] rank;     // rank[i]表示以i为根的集合树的深度

    public UnionFind4(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0 ; i < size ; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    // 查看元素p和q是否同属一个集合
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    // 合并元素p和q的集合，O(h)
    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) return;

        // 根据两个元素所在树的深度不同判断合并的方向
        // 将深度小的集合合并到深度大的集合
        if (rank[pRoot] < rank[qRoot]) {
            parent[pRoot] = qRoot;
        }
        else if (rank[qRoot] < rank[pRoot]) {
            parent[qRoot] = pRoot;
        }
        else {
            parent[pRoot] = qRoot;
            rank[qRoot]++;
        }
    }

    // 查找元素p所对应的集合编号，O(h)
    private int find(int p) {
        if (p < 0 || p >= id.length) throw new IllegalArgumentException("out of bound");
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }
}

Union Find V - 简易路径压缩(非递归)

  在树结构的并查集中，为了效率，我们希望树的深度越小越好
  因此可以采用路径压缩，在find过程中进行路径压缩
  时间复杂度: 严格意义上，O(log * n) -> iterated logarithm << O(logn)，近乎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
59
public class UnionFind5 implements UF {

    private int[] parent;   // parent数组
    private int[] rank;     // rank[i]表示以i为根的集合树的深度

    public UnionFind5(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0 ; i < size ; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    // 查看元素p和q是否同属一个集合
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    // 合并元素p和q的集合，O(h)
    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) return;

        // 根据两个元素所在树的深度不同判断合并的方向
        // 将深度小的集合合并到深度大的集合
        if (rank[pRoot] < rank[qRoot]) {
            parent[pRoot] = qRoot;
        }
        else if (rank[qRoot] < rank[pRoot]) {
            parent[qRoot] = pRoot;
        }
        else {
            parent[pRoot] = qRoot;
            rank[qRoot]++;
        }
    }

    // 查找元素p所对应的集合编号，O(h)
    private int find(int p) {
        if (p < 0 || p >= id.length) throw new IllegalArgumentException("out of bound");
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];  // 简易路径压缩，将该节点的父节点改为其“爷爷”节点
                                            // 因此每次find，都会减少树的深度
                                            // 这里，没有必要去维护rank数组，在IV中我们定义rank
                                            // 为树的深度，而此时rank可以代表相对排名
            p = parent[p];
        }
        return p;
    }
}

Union Find VI - 递归路径压缩(find)

  在UnionFindV中，采用了简易路径压缩，每一次find都有很大可能导致新的路径压缩
  因此可以采用递归路径压缩，尽可能减少find时路径压缩的次数，但不代表性能的提升

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
public class UnionFind6 implements UF {

    private int[] parent;   // parent数组
    private int[] rank;     // rank[i]表示以i为根的集合树的深度

    public UnionFind6(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0 ; i < size ; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    // 查看元素p和q是否同属一个集合
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    // 合并元素p和q的集合，O(h)
    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) return;

        // 根据两个元素所在树的深度不同判断合并的方向
        // 将深度小的集合合并到深度大的集合
        if (rank[pRoot] < rank[qRoot]) {
            parent[pRoot] = qRoot;
        }
        else if (rank[qRoot] < rank[pRoot]) {
            parent[qRoot] = pRoot;
        }
        else {
            parent[pRoot] = qRoot;
            rank[qRoot]++;
        }
    }

    // 查找元素p所对应的集合编号，O(h)
    private int find(int p) {
        if (p < 0 || p >= id.length) throw new IllegalArgumentException("out of bound");
        // 递归路径压缩
        if (p != parent[p]) {
            parent[p] = find(parent[p]);
        }
        return parent[p];
    }
}

------------------------ The End ------------------------

本文标题:并查集(Union Find)

文章作者:Lu, Ruihui

发布时间:2020年05月30日 - 02:39:55

最后更新:2021年04月13日 - 19:08:18

原始链接:https://github.com/cs-lurh0826/cs-lurh0826.github.io/Data-Structure/union-find/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

一花一世界，一叶一追寻