一起学习交流~

并查集

算法 laomuji 7个月前 (03-02) 460次浏览 已收录 0个评论

概念

并查集(Union Find)也叫「不相交集合(Disjoint Set)」,专门用于 动态处理 不相交集合的「查询」与「合并」问题。
可以使用并查集的问题一般都可以使用基于遍历的搜索算法(深度优先搜索、广度优先搜索)完成,但是使用并查集会使得解决问题的过程更加清晰、直观。
并查集的问题属于竞赛级别需要掌握的数据结构,但其本身代码量少且好理解,但难在应用。
一般需要实现两个函数
find和union,用于查询根节点和连接两条边

题目

使用力扣的684题冗余连接
https://leetcode-cn.com/problems/redundant-connection/
例题 测试数据不够多,可能看不出区别
学完后做下面这个题,不用优化算法是会超时的
https://leetcode-cn.com/problems/number-of-operations-to-make-network-connected/

quick find

quick find 用于快速查找是否属于同一个集合,但连接较慢

class Solution {
private:
    class UnionFind{//quick find 实现
    public:
        vector<int>root;//存放节点对应的根节点
        UnionFind(int n){
            root.resize(n);
            for(int i =0;i<n;i++){
                root[i]=i;
            }
        }
        int find(int x){
            return root[x];
        }
        void unionXY(int x,int y){
            int rootX = find(x);
            int rootY = find(y);
            //若两个集合的根节点不同
            //则把其它一个集合的所有节点都指向另一个节点
            if(rootX != rootY){
                for(int i =0;i<root.size();i++){
                    if(root[i]==rootY){//这里是随机选取的,缺点是可能会很慢
                        root[i]=rootX;
                    }
                }
            }
        }
    };
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int size = edges.size()+1;//因为下标从1开始 所以要+1
        UnionFind uf(size);
        vector<int>result;
        for(const vector<int>&edge : edges){
            if(uf.find(edge[0]) == uf.find(edge[1])){
                //如果根节点相同,那么已经连接过了,是冗余的边
                result = edge;
            }else{
                //如果根节点不同,那么可以连接
                uf.unionXY(edge[0],edge[1]);
            }
        }
        return result;
    }
};

quick union

和quick find 相反 这个用于快速连接,但查询较慢

class Solution {
private:
    class UnionFind{//quick union 实现
    public:
        vector<int>root;//存放节点对应的根节点
        UnionFind(int n){
            root.resize(n);
            for(int i =0;i<n;i++){
                root[i]=i;
            }
        }
        int find(int x){
            while(x!=root[x]){
                x=root[x];//一层层的往上查找
            }
            return x;
        }
        void unionXY(int x,int y){
            int rootX = find(x);
            int rootY = find(y);
            //若两个集合的根节点不同
            //则把一个节点的根节点指向另一个根节点
            if(rootX != rootY){
                root[rootY]=rootX;
            }
        }
    };

public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int size = edges.size()+1;//因为下标从1开始 所以要+1
        UnionFind uf(size);
        vector<int>result;
        for(const vector<int>&edge : edges){
            if(uf.find(edge[0]) == uf.find(edge[1])){
                //如果根节点相同,那么已经连接过了,是冗余的边
                result = edge;
            }else{
                //如果根节点不同,那么可以连接
                uf.unionXY(edge[0],edge[1]);
            }
        }
        return result;
    }
};

按秩合并

之前的根节点是随机合并的,某些极端情况下会退化为类似链表,很多层 很慢
此时 多引入一个数组 记录根节点的高度
将较小的高度合并到较高的高度上
若高度相同则随机合并,并且高度会增大1

class Solution {
private:
    class UnionFind{//按秩合并
    public:
        vector<int>root;//存放节点对应的根节点
        vector<int>rank;//存放节点对应的高度
        UnionFind(int n){
            root.resize(n);
            rank.resize(n);
            for(int i =0;i<n;i++){
                root[i]=i;
                rank[i]=1;
            }
        }
        int find(int x){
            while(x!=root[x]){
                x=root[x];//一层层的往上查找
            }
            return x;
        }
        void unionXY(int x,int y){
            int rootX = find(x);
            int rootY = find(y);
            //若两个集合的根节点不同
            //则按秩合并
            if(rootX != rootY){
                if(rank[rootX] > rank[rootY]){
                    root[rootY]=rootX;//短的连接高的,高度不变
                }else if(rank[rootX] < rank[rootY]){
                    root[rootX]=rootY;//短的连接高的,高度不变
                }else{
                    root[rootY]=rootX;
                    rank[rootX]++;//因为两个相同的高度合并了,高度增加了1
                }
            }
        }
    };

public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int size = edges.size()+1;//因为下标从1开始 所以要+1
        UnionFind uf(size);
        vector<int>result;
        for(const vector<int>&edge : edges){
            if(uf.find(edge[0]) == uf.find(edge[1])){
                //如果根节点相同,那么已经连接过了,是冗余的边
                result = edge;
            }else{
                //如果根节点不同,那么可以连接
                uf.unionXY(edge[0],edge[1]);
            }
        }
        return result;
    }
};

路径压缩

查询时,每次都要往上找,层数高的话会非常慢
那么 可以记录经过的值, 使每个节点都记录根节点的值

class Solution {
private:
    class UnionFind{//路径压缩的实现,高度不会超过两层
    public:
        vector<int>root;//存放节点对应的根节点
        UnionFind(int n){
            root.resize(n);
            for(int i =0;i<n;i++){
                root[i]=i;
            }
        }
        int find(int x){
            if(root[x]==x)return x;//如果是根节点直接返回
            //如果不是根节点,则递归寻找根节点,并修改记录
            root[x] = find(root[x]);
            return root[x];
        }
        void unionXY(int x,int y){
            int rootX = find(x);
            int rootY = find(y);
            if(rootX != rootY){//高度不会超过两层,不需要循环修改
                root[rootY]=rootX;
            }
        }
    };
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int size = edges.size()+1;//因为下标从1开始 所以要+1
        UnionFind uf(size);
        vector<int>result;
        for(const vector<int>&edge : edges){
            if(uf.find(edge[0]) == uf.find(edge[1])){
                //如果根节点相同,那么已经连接过了,是冗余的边
                result = edge;
            }else{
                //如果根节点不同,那么可以连接
                uf.unionXY(edge[0],edge[1]);
            }
        }
        return result;
    }
};
喜欢 (0)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论