Java-并查集

发表于 | 分类于 | 阅读次数:

并查集（Union Find）

什么是并查集

并查集是一种树型的数据结构，其保持着用于处理一些 不相交集合（Disjoint Sets）的 合并及查询 问题。其包含合并集合 和 查找集合中的元素 两种操作。并且其常用于解决 动态连通性一类问题

实现

并查集实现有两种方式 分别是： 简单元素替换 和 代表元素合并

Quick Find

可以将该方法考虑为，为数据分为不同的集合，每次合并一个新的元素进来的时候，都要将原来集合里所有元素的值都修改为新并入元素的值。实现简单就是每次更新需要遍历一遍集合

1
2
3
4
5
6
7
public interface UF {
    int getSize();

    boolean isConnected(int p, int q);

    void unionElements(int p, int q);
}
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 implements UF {

    private int[] id;

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

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

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

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(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;
        }
    }
}

它查找元素的时间复杂度非常低，只有O(1)，而合并集合元素的时候时间复杂度达到了O(N)。这种实现看起来还可以，就是感觉合并的时候似乎慢了一点，那么有没有办法使得合并的操作快点呢？

Quick Union

和前面归并元素的思路不同，这里采用的是一种类似于树的层次结构。我们可以创建一个 parent 数组，数组元素值是其下标的父节点。按照这个思路，如果我们将一个元素并入到一个集合的时候，我们可以修改这个集合的代表元素，只要这个代表元素的值为这个并入的元素就可以了

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

    // 我们的第二版Union-Find, 使用一个数组构建一棵指向父节点的树
    // parent[i]表示第一个元素所指向的父节点
    private int[] parent;

    // 构造函数
    public UnionFind2(int size){

        parent = new int[size];

        // 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
        for( int i = 0 ; i < size ; i ++ )
            parent[i] = i;
    }

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

    // 查找过程, 查找元素p所对应的集合编号
    // O(h)复杂度, h为树的高度
    private int find(int p){
        if(p < 0 || p >= parent.length)
            throw new IllegalArgumentException("p is out of bound.");

        // 不断去查询自己的父亲节点, 直到到达根节点
        // 根节点的特点: parent[p] == p
        while(p != parent[p])
            p = parent[p];
        return p;
    }

    // 查看元素p和元素q是否所属一个集合
    // O(h)复杂度, h为树的高度
    @Override
    public boolean isConnected( int p , int q ){
        return find(p) == find(q);
    }

    // 合并元素p和元素q所属的集合
    // O(h)复杂度, h为树的高度
    @Override
    public void unionElements(int p, int q){

        int pRoot = find(p);
        int qRoot = find(q);

        if( pRoot == qRoot )
            return;

        parent[pRoot] = qRoot;
    }
}

这种实现里，查找所在集合的代表元素需要遍历它的父节点，直到它和它的下标值相同。但是归并的时候只要修改一个元素的值就可以了。不过从最坏的情况来看，查找这个集合的根节点的时间复杂度就可能将近O(N)了。看来这个办法是使得归并的操作简单了，但是整体的时间复杂度并没有完全降下去。

那么还有没有什么办法可以改进呢？

优化

在前面的 代替元素合并 方法中，会有极端的情况是因为，没有合并集合时进行判断，如果集合越来越长，也就退化成为了链表。所以，我们可以在这里进行优化，将要合并的两个集合进行判断（元素数量或高度），把数值低的纳入在高的下面，可以大大提升效率

基于Size优化

基于 Size 优化并不如基于 Rank 优化效果好，而且代码也很简单，所以就不详细列出了。若有兴趣，可以观察下面的代码，进行仿写。

基于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
56
57
58
59
60
61
62
63
64
65
66
public class UnionFind4 implements UF {

    private int[] rank;   // rank[i]表示以i为根的集合所表示的树的层数
    private int[] parent; // parent[i]表示第i个元素所指向的父节点

    // 构造函数
    public UnionFind4(int size){

        rank = new int[size];
        parent = new int[size];

        // 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
        for( int i = 0 ; i < size ; i ++ ){
            parent[i] = i;
            rank[i] = 1;
        }
    }

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

    // 查找过程, 查找元素p所对应的集合编号
    // O(h)复杂度, h为树的高度
    private int find(int p){
        if(p < 0 || p >= parent.length)
            throw new IllegalArgumentException("p is out of bound.");

        // 不断去查询自己的父亲节点, 直到到达根节点
        // 根节点的特点: parent[p] == p
        while(p != parent[p])
            p = parent[p];
        return p;
    }

    // 查看元素p和元素q是否所属一个集合
    // O(h)复杂度, h为树的高度
    @Override
    public boolean isConnected( int p , int q ){
        return find(p) == find(q);
    }

    // 合并元素p和元素q所属的集合
    // O(h)复杂度, h为树的高度
    @Override
    public void unionElements(int p, int q){

        int pRoot = find(p);
        int qRoot = find(q);

        if( pRoot == qRoot )
            return;

        // 根据两个元素所在树的rank不同判断合并方向
        // 将rank低的集合合并到rank高的集合上
        if(rank[pRoot] < rank[qRoot])
            parent[pRoot] = qRoot;
        else if(rank[qRoot] < rank[pRoot])
            parent[qRoot] = pRoot;
        else{ // rank[pRoot] == rank[qRoot]
            parent[pRoot] = qRoot;
            rank[qRoot] += 1;   // 此时, 我维护rank的值
        }
    }
}

路径压缩

经过上面的优化，效率已经有了很大的提升。在运行中，有很大的一部分时间是花在了，通过一个节点查找其根节点上。我们要是在这个时间段上，进行路径的压缩会不会更有效果那？

非递归路径压缩
1
2
3
4
5
6
7
8
9
10
private int find(int p){
    if(p < 0 || p >= parent.length)
        throw new IllegalArgumentException("p is out of bound.");

    while(p != parent[p]){
        parent[p] = parent[parent[p]];
        p = parent[p];
    }
    return p;
}

进行简单的路径压缩，只需要对 基于Rank 优化的代码中 find方法 进行改动即可

代码含义是 ： 把从当前叶节点到向上每两层的节点都指向自己的祖父节点

递归路径压缩
1
2
3
4
5
6
7
8
9
private int find(int p){
    if(p < 0 || p >= parent.length)
        throw new IllegalArgumentException("p is out of bound.");

    if(p != parent[p]){
        parent[p] = find(parent[p]);
    }
    return parent[p];
}

如此改动之后，则会将所有元素，指向根节点。

添加路径压缩后，并查集的时间复杂度是 O(log*n) ，比 O(log(n)) 还要快一点

相关问题

主要用于解决动态连接性问题，LeetCode上面有并查集的标签可以尝试一下