Union-find 算法笔记

问题描述

问题的输入是一列整数对, 其中每个整数都有表示一个某种类型的对象, 一对整数 p, q 可以理解为” p 和 q 是相连的”. 假设, 相连是一种等价关系, 它具有:

  • 自反性 : p 和 p是相连的
  • 对称性 : 若 p 和 q 相连, 则 q 和 p 也相连
  • 传递性 : 若 p 和 q 相连, 且 q 和 r 相连, 则 p 和 r 相连 现在, 给定点的数目和一些坐标点矩阵(x, y) 其中 x, y ∈ Z 代表 x 和 y 相连, 要求找出整个点矩阵拥有的连通分量数目, 例如:
    输入: 
    1
    2
    3
    4
    5
    6
    7
    8
    8 
    0 1
    2 3
    0 4
    2 6
    3 7
    4 5
    6 7
    输出:
    1
    2
    解释:
    按要求画出连通图
    其中 6, 7 之间连通是不必要的, 且此点阵 0, 1, 4, 5 间连通, 2, 3, 6, 7 间连通, 拥有两个连通分量

    输入样本:
    10个点
    625个点
    1000000个点

解决方案

程序将按以下的 API 编写

方法签名 注释
UnionFind (int N) 初始化 N 个点
void union (int p, int q) 将 p 和 q 连通
int find (int p) 找出点 p 所属的分量标识
boolean connected (int p, int q) 判断 p 和 q 之间是否连通
int count () 连通分量数量

Quick-find

这种算法维护着一个整形数组 id[], 数组下标是点的序号, 值为点所属的分量标识.
刚开始是每个点都是一个连通分量, 当要连接两个连通分量时, 需要把一个连通分量中的所有点所属的分量标识改为与另一个连通分量相同.

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
public class UnionFind {

    private final int[] id;
    private int count; // 连通分量数量


    public UnionFind(int number) {
        id = new int[number];
        count = number;

        for (var i = 0; i < id.length; i++) {
            id[i] = i;
        }

    }

    public void union(int p, int q) {

        if (!isConnected(p, q)) {
            var qId = find(q);
            var pId = find(p);

            for (int i = 0; i < id.length; i++)
                if (id[i] == qId)
                    id[i] = pId;

            count--;
        }

    }


    public int find(int p) {
        return id[p];          
    }

    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    public int count() {
        return count;
    }
}

这种算法的时间复杂度为:

  • 构造函数: O(N) = N
  • union(): O(N) = N
  • find(): O(N) = 1
    这种算法中的 union() 方法的数组访问次数最坏是 N^2 次, 当解决输入规模较大的问题时将会非常吃力

Quick-union 算法

这种算法维护着一个整形数组 id[], 数组下标是点的序号, 值为比这个点序号大, 同时属于同一个连通分量的点的序号.
一个连通分量中序号最大的点的值指向自己.
刚开始是每个点都是一个连通分量, 当要连接两个连通分量时, 需要把一个连通分量序号最大的点的值改为另一个连通分量中任意点的序号.

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
public class UnionFind {

    private final int[] id;
    private int count; // 连通分量数量


    public UnionFind(int number) {
        id = new int[number];
        count = number;

        for (var i = 0; i < id.length; i++) {
            id[i] = i;
        }
    }

    public void union(int p, int q) {
        if (!isConnected(p, q)) { 
            var qId = find(q);
            var pId = find(p);

            id[pId] = qId;

            count--;
        }
    }

    public int find(int p) {
        while (p != id[p]){
            id[p] = id[id[p]];
            p = id[p];
        }

        return p;
    }

    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    public int count() {
        return count;
    }
}
例1 当输入: 
1
2
3
4
5
6
7
8
10
4 3
3 8
6 5
9 4
2 1
5 0
7 2

后树为

再次输入 6 1 后

这种算法的时间复杂度为:

  • 构造函数: O(N) = N
  • union(): O(N) = 树高
  • find(): O(N) = 树高
    这种算法的 find() 方法数组访问次数最坏是 N^2 次, 仍然不适合解决输入较大的问题

加权 Quick-union 算法

这种算法和 Quick-union 算法思想基本相同. 不一样的地方在于, 在连接两个树是, 总是将深度小的树连接到深度大的树上

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 UnionFind {

    private final int[] id;
    private final int[] size; // 各树对应的深度, 下标为点序号
    private int count; // 连通分量数量


    public UnionFind(int number) {
        id = new int[number];
        size = new int[number];
        count = number;

        for (var i = 0; i < id.length; i++) {
            id[i] = i;
            size[i] = 1;
        }
    }

    public void union(int p, int q) {

        if (!isConnected(p, q)) {
            var qId = find(q);
            var pId = find(p);
            if(size[pId] < size[qId]) {
                id[pId] = qId;
                size[qId] = Math.max(size[qId], size[pId] + 1);
            } else {
                id[qId] = pId;
                size[pId] = Math.max(size[qId] + 1, size[pId]);
            }

            count--;
        }

    }


    public int find(int p) {
        while (p != id[p]){
            p = id[p];
        }

        return p;
    }

    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    public int count() {
        return count;
    }
}

以 Quick-union 算法中的 例1 为例, 当最后输入 6 1 后, 树图为

这种算法的时间复杂度为:

  • 构造函数: O(N) = N
  • union(): O(N) = lbN
  • find(): O(N) = lbN
    这个算法在处理 N 个点 M条连接时, 最多访问 cMlbN (c为常数) 次数组, 能在合理的时间内解决大规模的输入问题

压缩加权 Quick-union 算法

这种算法和加权 Quick-union 算法思想基本相同. 不一样的地方在于, 在 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
57
58
public class UnionFind {

    private final int[] id;
    private final int[] size; // 各树对应的深度, 下标为点序号
    private int count; // 连通分量数量


    public UnionFind(int number) {
        id = new int[number];
        size = new int[number];
        count = number;

        for (var i = 0; i < id.length; i++) {
            id[i] = i;
            size[i] = 1;
        }
    }

    public void union(int p, int q) {

        if (!isConnected(p, q)) {
            var qId = find(q);
            var pId = find(p);
            if(size[pId] < size[qId]) {
                id[pId] = qId;
                size[qId] = Math.max(size[qId], size[pId] + 1);
            } else {
                id[qId] = pId;
                size[pId] = Math.max(size[qId] + 1, size[pId]);
            }

            count--;
        }

    }


    public int find(int p) {
        while (p != id[p]){
            p = id[p];
        }
        int result = p;
        while (p != id[p]){
            id[p] = result;
            p = id[p];
        }

        return result;
    }

    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    public int count() {
        return count;
    }
}

相比加权 Quick-union 算法, 这个算法对性能提升并不大.