并查集

并查集

通常用来解决 “ 连接问题” 。 并查集可以非常快速的判断网络中节点的连接状态，而这里所说的网络是一个抽象的概念：是指用户之间形成的网络。

“连接问题和路径问题”

通常情况下，解决一个连接问题，我们也可以用解决路径问题来代替，如果二者之间存在路径，那他们一定是连接的，反之亦然。如果我们只需要了解二者之间的连接状态的话，我们没有必要借助他们之间的路径来求，这样我们会消耗很多额外的性能。

对于并查集而言，对于一种数据，主要支持两个动作:

  • union(p,q) 将二者所在的集合合并
  • isConnected(p,q) 查询二者是否属于同一个集合

接口的定义如下所示

1
2
3
4
5
public interface UF {
    boolean isConnected(int p,int q);
    void unionElements(int p,int q);
    int getSize();
}

接下来我们实现第一版的并查集 —->QuickFind

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
/**
 * 使用数组，达到查询操作O(1)的时间复杂度
 * 但是Union时间复杂度为O(n)
 */
public class QuickFind implements UF {

    private int []id;
    public QuickFind(int size){
        id =new int[size];
        for(int i=0;i<id.length;i++){
            //初始情况下，任意两个元素都不属于同一个集合
            id[i]=i;
        }
    }

    /**
     * 查看元素p和元素q是否所属同一个集合
     * @param p
     * @param q
     * @return
     */
    @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(qID==pID){
            //当前元素p和q已经连接了
            return ;
        }
        for(int i=0;i<id.length;i++){
            //这里也可以改成  id[i]==qID
                          // id[i]=pID;
             if(id[i]==pID){
                 id[i]=qID;
             }
        }

    }

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

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

事实上，我们很少用到这样的并查集，因为其合并操作的时间复杂度达到了O(n),在数据量大的情况下，这种方式是不可取的。

接下来我们实现第二版的并查集 —->QuickUnion

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
/**
 * 用树来构造，孩子节点指向父亲节点，父亲节点自带一个指针指向自己
 * Union的时间复杂度为O(h),其中h为Union的这两棵树的深度的大小
 * find的时间复杂度也为O(h)
 */
public class QuickUnion implements UF {
    //记录第i个元素指向哪个节点
    private int[]parent;

    public QuickUnion(int size){

        parent=new int[size];
        for (int i = 0; i < size; i++) {
            //初始时，让每个节点都指向自己
            parent[i]=i;
        }
    }

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

    /**
     * 合并元素p和元素q所属的集合
     * O(h)时间复杂度，h为树的高度
     * @param p
     * @param q
     */
    @Override
    public void unionElements(int p, int q) {
        int qRoot=find(q);
        int pRoot=find(p);
       if(qRoot==pRoot) return ;
       parent[pRoot]=qRoot;
    }

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

    /**
     * 从当前节点开始，一直往根节点寻找
     * 时间复杂度为O(h)
     * @param p
     * @return
     */
    private int find(int p){
        if(p<0||p>=parent.length){
            throw new IllegalArgumentException("p is out of bound");
        }
         while(p!=parent[p]){
             p=parent[p];
         }
         return p;
    }
}

实际上，在QuickUnion中，我们使用数组模拟了一棵“奇怪的树” ，或者来说，在初始情况下，叫“森林” 。因为初始情况下，有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
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
67
68
69
70
71
72
73
74
75
76
77
78
public class QuickUnion_size implements UF {

    //记录第i个元素指向哪个节点
    private int[]parent;
    //sz[i]表示以i为根的集合中元素个数
    private int []sz;

    public QuickUnion_size(int size){

        parent=new int[size];
        sz=new int[size];
        for (int i = 0; i < size; i++) {
            //初始时，让每个节点都指向自己
            parent[i]=i;
            sz[i]=1;
        }
    }

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

    /**
     * 合并元素p和元素q所属的集合
     * O(h)时间复杂度，h为树的高度
     * @param p
     * @param q
     */
    @Override
    public void unionElements(int p, int q) {
        int qRoot=find(q);
        int pRoot=find(p);
        if(qRoot==pRoot) return ;
        if(sz[pRoot]<sz[qRoot]){
            //让节点个数少的指向节点个数多的
            parent[pRoot]=qRoot;
            //更新节点数
            sz[qRoot]+=sz[pRoot];
        }else{
            //sz[pRoot]>=sz[qRoot]
            parent[qRoot]=pRoot;
            sz[pRoot]+=sz[qRoot];
        }




    }

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

    /**
     * 从当前节点开始，一直往根节点寻找
     * 时间复杂度为O(h)
     * @param p
     * @return
     */
    private int find(int p){
        if(p<0||p>=parent.length){
            throw new IllegalArgumentException("p is out of bound");
        }
        while(p!=parent[p]){
            p=parent[p];
        }
        return p;
    }
}

上述的优化还是会存在一些问题，我们更应该考虑一个并查集的高度值，而不是其节点的个数。

这种思想，在并查集中，更为普遍的说法叫“基于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
67
68
69
70
71
72
73
74
75
76
77
78
public class QuickUnion_Rank implements UF {

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

    public QuickUnion_Rank(int size){

        parent=new int[size];
        rank=new int[size];
        for (int i = 0; i < size; i++) {
            //初始时，让每个节点都指向自己
            parent[i]=i;
            //初始时，层数为1
            rank[i]=1;
        }
    }

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

    /**
     * 合并元素p和元素q所属的集合
     * O(h)时间复杂度，h为树的高度
     * @param p
     * @param q
     */
    @Override
    public void unionElements(int p, int q) {
        int qRoot=find(q);
        int pRoot=find(p);
        if(qRoot==pRoot) return ;
       //根据两个元素所在树的Rank不同判断合并方向
        //将rank低的集合指向rank高的集合上
        if(rank[qRoot]<rank[pRoot]){
            parent[qRoot]=pRoot;
            //此时高度并没有变化，不必维护rank数组
        }else if(rank[pRoot]<rank[qRoot]){
            parent[pRoot]=qRoot;

        }else{
            parent[qRoot]=parent[pRoot];
            //高度相等，要维护rank
            rank[pRoot]+=1;
        }
    }

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

    /**
     * 从当前节点开始，一直往根节点寻找
     * 时间复杂度为O(h)
     * @param p
     * @return
     */
    private int find(int p){
        if(p<0||p>=parent.length){
            throw new IllegalArgumentException("p is out of bound");
        }
        while(p!=parent[p]){
            p=parent[p];
        }
        return p;
    }
}

接下来我们来进行使用并查集时， 最经典的一个优化操作 “路径压缩”**

在我们查找一个元素的根节点时，我们是一层一层往上查询，在寻找的过程中，我们顺便让深度降低，及达到路径压缩的目的。我们在向上搜索时，执行 parent[p]=parent[parent[p]]。

实际上，要完成上述步骤，非常容易，我们只用在find操作中添加一行代码

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;
}

这样的话，将会大大改善并查集的性能！

赏

谢谢你请我喝奶茶

微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家