当前位置：首页 > article >正文

并查集（Union-Find）

article 2024/10/19 19:44:45

并查集（Disjoint Set，也称为Union-Find数据结构）是一种用于高效处理不相交集（即集合内元素互相独立，没有交集）的数据结构。它主要用于解决以下两种操作：

查找（Find）：确定某个元素所属的集合。
合并（Union）：将两个不相交的集合并为一个集合。

并查集通常在解决诸如连通性问题、最小生成树算法（如Kruskal算法）和图论中的其他问题时非常有用。

并查集的核心思想

并查集使用树形结构来表示集合，每一个集合对应一棵树，树的根节点作为集合的代表元素。主要操作如下：

初始化：每个元素都作为一个单独的集合（即每个元素作为一棵单节点的树）。
查找：通过递归或迭代找到元素所在树的根节点，根节点即代表该集合。
合并：将两棵树的根节点相连，使得一棵树成为另一棵树的子树。

优化方法

为了提高并查集的性能，通常采用以下两种优化方法：

路径压缩（Path Compression）：在查找操作中，将查找路径上遇到的所有节点直接连接到根节点，以减少未来的查找时间。
按秩合并（Union by Rank）：在合并操作中，将秩（树的深度）较小的树连接到秩较大的树的根节点，以保持树的平衡。

核心代码

以下是使用Java实现并查集的基本代码：

class UnionFind {
    private int[] parent; // 保存每个节点的父节点
    private int[] rank;   // 保存每个节点的秩（树的深度）

    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i; // 初始化时每个节点作为自己的父节点
            rank[i] = 0;   // 初始秩为0
        }
    }

    // 查找操作，路径压缩
    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) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX; // 将秩较小的树连接到秩较大的树
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++; // 如果秩相同，合并后秩增加1
            }
        }
    }

    // 判断两个节点是否在同一个集合中
    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
}