数据结构--并查集

2023-03-21

字数统计: 1.4k字 | 阅读时长≈ 6分

并查集是一种用于处理集合合并及查询问题的数据结构

它主要支持两种操作：合并（Union）和查找（Find）

基本思想：将每个元素看作一个节点，每个节点都有一个父节点，如果两个节点的父节点相同，则它们属于同一个集合。初始时，每个节点的父节点都是它自己，表示每个节点都是一个独立的集合。当两个节点需要合并时，只需要将其中一个节点的父节点指向另一个节点的父节点即可。并查集的查找操作是通过递归查找父节点来实现的。

应用：在图论中用于判断两个节点是否连通，以及在最小生成树算法中用于判断是否形成环等

并查集的时间复杂度主要取决于集合的深度，因此在实际应用中需要注意尽量避免出现深度过大的情况，可以通过路径压缩等优化方式来减小集合的深度。

并查集：

根据集合深度合并：

public class UnionFind {
    private int[] parents;//用于存储每个结点的父节点
    private int[] ranks;//用于存储每个结点所在集合的深度

    //初始化时，每个结点的父节点都是它自己，树的深度都为1
    public UnionFind(int n) {
        parents = new int[n];
        ranks = new int[n];
        for (int i = 0; i < n; i++) {
            parents[i] = i;
            ranks[i] = 1;
        }
    }

    //用于查找结点x所在的集合的根节点
    //如果x的父节点不是根节点，则递归查找x的父节点，直到找到根节点。
    //在查找的过程中，使用路径压缩来优化树的深度，即将x到根节点路径上的所有节点的父节点都指向根节点。
    public int find(int x) {
        if (parents[x] != x) {
            parents[x] = find(parents[x]);//路径压缩
        }
        return parents[x];
    }

    //用于合并两个集合
    //首先找到x和y所在集合的根节点，如果它们的根节点相同，则它们已经在同一个集合中，不需要再合并。
    //否则，我们比较两个集合的深度，将小的集合合并到大的集合中（这样不会增加集合的深度）。
    //如果两个集合深度相同，则将其中一个集合合并到另一个集合中，并将合并集合深度加1。
    public void unionByRank(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return;
        }
        if (ranks[rootX] > ranks[rootY]) {
            parents[rootY] = rootX;
        } else if (ranks[rootX] < ranks[rootY]) {
            parents[rootX] = rootY;
        } else {
            parents[rootY] = rootX;
            ranks[rootX]++;
        }
    }
}

根据集合大小合并：

/**
 * 并查集
 * @author zzr
 * @create 2023-10-21-19:57
 */
public class UnionFind {
    int[] parents;//记录元素根集合
    int[] sizes;//根集合中元素个数

    /**
     * 初始化
     * @param n 元素范围（0~n）
     */
    public UnionFind(int n) {
        parents=new int[n];
        //元素初始根集合为自己
        for (int i = 0; i < n; i++) {
            parents[i]=i;
        }
        sizes=new int[n];
        //初始每个根集合元素个数为1
        Arrays.fill(sizes,1);
    }

    /**
     * 查找 元素根集合
     * @param x 元素(parents索引)
     * @return
     */
    public int find(int x){
        //索引和值相等，找到根集合(parents值)
        if (x==parents[x]){
            return parents[x];
        }
        //索引和值不相等，递归查找值的根集合
        //路劲压缩：查找到根集合返回过程中，更新查找过程元素的根集合为查找到的根集合，下次查找时可减少查找次数
        return parents[x]=find(parents[x]);
    }

    /**
     * 根据根集合中元素个数合并两个集合
     * @param x
     * @param y
     */
    public void unionBySize(int x,int y){
        int px = find(x);
        int py = find(y);
        //元素根集合不相等，进行合并
        if (px!=py){
            //小集合向大集合合并
            if (sizes[px]>=sizes[py]){
                parents[py]=px;
                sizes[px]+=sizes[py];
            }else {
                parents[px]=py;
                sizes[py]+=sizes[px];
            }
        }
    }

    /**
     * 获取集合元素个数
     * @param x 集合
     * @return
     */
    public int getSize(int x){
        return sizes[x];
    }
}

应用：

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份：是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中省份的数量。

示例 1：

输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]

输出：2

示例 2：

输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]

输出：3

来源：力扣（LeetCode）547题

链接：https://leetcode.cn/problems/number-of-provinces

class Solution {
    public int findCircleNum(int[][] isConnected) {
    UnionFind unionFind = new UnionFind(isConnected.length);
    for (int i = 0; i < isConnected.length; i++) {
            for (int j = i + 1; j < isConnected.length; j++) {
                if (isConnected[i][j] == 1) {
                    unionFind.union(i, j);
                }
            }
        }
        return unionFind.getCount();
    }
}

class UnionFind{
    private int[] parent;
    private int[] rank;
    private int count;

    public UnionFind(int n){
        parent=new int[n];
        rank=new int[n];
        count=n;
        for (int i = 0; i < n; i++) {
            parent[i]=i;
            rank[i]=1;
        }
    }

    public int find(int x){
        if (parent[x]!=x){
            parent[x]=find(parent[x]);
        }
        return parent[x];
    }

    public void union(int x,int y){
        int rootX = find(x);
        int rootY = find(y);
        if (rootX==rootY){
            return;
        }
        if (rank[rootX]>rank[rootY]){
            parent[rootY]=rootX;
        }else if(rank[rootX] < rank[rootY]){
            parent[rootX]=rootY;
        }else{
            parent[rootY]=rootX;
            rank[rootX]++;
        }
        count--;
    }

    public int getCount() {
        return count;
    }
}

本文作者： zzr
本文链接： http://zzruei.github.io/2023/03fcff9e09.html
版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！