并查集——解决连接问题的神器

本文阅读 8 分钟
首页 代码,Java 正文

目录

1 定义

2 Quick Find实现

3 Quick Union

4 基于size的优化

5 基于rank的优化

6 路径压缩

并查集是一种很不一样的树形结构,由子节点指向父节点。常被用来回答连接问题(Connectivity Problem),比如下图中求左上角的点和右下角的点是否相连,我们难以用肉眼观察出结果,需要借助这样的数据结构来帮助我们解决。

 

img

网络是个抽象的概念:

社交软件的用户,购物网站的商品信息,交通系统等等都可以抽象成网络中的节点,所以实际中的很多问题都可以借助这个强大的数据结构来解决。

 

除了解决连接问题,并查集还是数学中集合这一概念的具体实现,并查集的“并”字其实也是数学集合求并集的概念。

 

主要支持两个动作:

 

// 将两个数据合并起来
union(p,q);
// 判断p,q是否相连
isConnected(p,q);

程序框架(接口)如下:

 

public interface UF {
    int getSize();
    boolean isConnected(int p, int q);
    void unionElements(int p, int q);
}

其中p和q表示id,即数组的索引

 

 

 

在并查集内部,可以为每一个数据索引 p 或 q 分配一个编号id

 

img

判断p,q是否属于同一个集合只需查看对应的id是否相同即可。

我们可以定义一个函数 find(p) 来寻找p所对应的分组,相应的isConnected方法会调用find

 

img

这样设计的并查集查询操作的时间复杂度为O(1),所以被称为quick find

 

public class UnionFind1 implements UF {

    private int[] id;    // 本质就是一个数组

    public UnionFind1(int size) {
        id = new int[size];
        // 初始化, 每一个id[i]指向自己, 没有合并的元素
        for (int i = 0; i < size; i++)
            id[i] = i;
    }

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

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

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

    // 合并元素p和元素q所属的集合
    // O(n) 复杂度
    @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;
    }
}

其中合并方法 unionElements(int p, int q) 需要单独解释一下,还是上面的例子,如果此时要合并1和4,那么意味着1所在的组和4所在的组合并

 

img

img

 

 

不过我们真实实现并查集时,是将每一个元素看作是一个节点,节点之间形成树,只是这棵树是子节点指向父节点的。

例如一个以2为根节点的树:

 

img

如果此时另外的节点1要和3进行合并,需要将节点1指向3的根节点

 

img

如果有另外一棵以5为根的树,其中节点7要和节点3合并,那么结果是将节点5指向节点2

 

img

在这种情况下我们依然可以用数组来进行存储,因为每一个节点只有一个指针指向别人。定义一个parent数组,parent[i]的值表示i指向的节点。初始形状如下:

 

img

img

此时如果要进行union(4,3)操作

 

img

对应数组里的

 

img

对应数组里的

 

img

对应数组中的

 

img

再进行union(9, 4)时,需要进行查找,4的父节点是3,3的父节点是8,8是根节点所以9指向8

 

img

时间复杂度:

union过程:O(h),其中h为树的高度,h << n。相应的查询过程的时间复杂度也是O(h)。

 

 

public class UnionFind2 implements UF {

    // 使用一个数组构建一棵指向父节点的树
    // 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;
    }
}

之后的代码都基于此来进行优化。

 

 

上面的例子中,如果依次执行union(0, 1),union(0, 2),union(0, 3),union(0, 4)...则会退化成一个链表,一个简单的解决方案是考虑当前的树有多少个节点。

假设并查集如下:

 

img

如果让8指向9的话,最终会得到一颗深度为4的树,但如果让9指向8只会得到一颗高度为3的树。

 

定义一个sz数组用于记录以i为根的集合中元素个数,union是将sz小的集合的根节点指向sz大的集合的根节点。

 

 

核心代码:

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{ // sz[qRoot] <= sz[pRoot]
            parent[qRoot] = pRoot;
            sz[pRoot] += sz[qRoot];
        }
}

 

 

rank指树的高度。

对于下面这个例子:

 

img

基于上面基于size优化的代码,节点数小的树指向节点数大的树,union(4, 2)将使得8指向7,将形成一颗高度为4的树,更加合理的合并方案是将7指向8,深度为3。

 

所以我们在真正合并时应该用深度代替size来决定谁指向谁。

 

核心代码:

 

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的值
        }
}

 

上面的代码还是有可能出现退化成链表的情况

 

img

由于树的高度决定并查集的性能,所以可以考虑使用路径压缩来尽力降低树的高度。

 

路径压缩:

讲一课比较高的树变为比较矮的树。

 

可以将路径压缩过程设计成执行find操作的时候,在寻找的过程中顺便执行路径压缩。路径压缩可以采用如下的方式:

 

parent[p] = parent[parent[p]];

即将p的父节点设置为其爷爷节点。

在find(4)时,将4的父节点设为2:

 

img

继续向上查找,2的父节点变为0

 

img

执行完毕之后树的深度从原先的5降低至现在的3。

 

核心代码:

 

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]];  // 路径压缩,添加后rank不再表示树的高度的物理意义,但是依然有效
            p = parent[p];
        }
        return p;
    }

至此我们对于并查集的优化完全结束。

 

完整代码:

 

/*
quick union
基于rank(树的层数)的优化
路径压缩
 */
public class UnionFind implements UF{
    private int[] parent;
    private int[] rank;   // sz[i]表示以i为根的集合中元素个数

    public UnionFind(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对应的集合编号
    // O(h),h为树高度
    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]];  // 路径压缩,添加后rank不再表示树的高度的物理意义,但是依然有效
            p = parent[p];
        }
        return p;
    }

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

    // 合并过程,合并pq所属的集合
    // 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高的树的根节点
        if (rank[pRoot] < rank[qRoot]){
            parent[pRoot] = qRoot;
            // 高度低的树的根指向高度高的树的根,总的高度不变不用维护rank
        }
        else if (rank[qRoot] < rank[pRoot]){
            parent[qRoot] = pRoot;
        }
        else {  // rank[qRoot] == rank[pRoot]
            parent[qRoot] = pRoot;
            rank[pRoot] += 1;
        }
    }
}

 

 

 

本文为互联网自动采集或经作者授权后发布,本文观点不代表立场,若侵权下架请联系我们删帖处理!文章出自:https://wangjiawei.blog.csdn.net/article/details/108668342
-- 展开阅读全文 --
安全面试之XSS(跨站脚本攻击)
« 上一篇 07-24

发表评论

成为第一个评论的人

热门文章

标签TAG

最近回复