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

并查集 (Union-Find) ：从基础到优化

article 2024/9/29 3:44:16

并查集 (Union-Find)

并查集是一种树形数据结构，主要用于处理不相交集合（Disjoint Set）的合并和查询问题。它特别适用于解决有关连通性的问题，比如在图论中判断两点是否在同一个连通分量中。并查集可以高效地支持以下两种操作：

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

属于集合关系

基础数据结构

每个集合最初由一个元素构成，每个元素都是自己集合的代表。可以用一个数组 parent 来保存每个元素的父节点。而合并操作则在不考虑树的深度的情况下直接将一个集合的根节点指向另一个集合的根节点。

初始化

用一个数组 parent 来表示集合，其中 parent[i] 表示节点 i 的父节点。初始化时，每个元素的父节点都是它自己，即每个元素都是自己集合的代表。

int[] parent = new int[n];
for (int i = 0; i < n; i++) {
    parent[i] = i;  // 每个元素的父节点指向自己
}

查找（Find）

查找操作用于找到元素所在集合的代表节点（根节点）。通过沿着父节点不断往上查找，直到找到一个节点，它的父节点是它自己，也就找到了根节点。

int find(int x) {
    while (parent[x] != x) {
        x = parent[x];  // 沿着父节点向上查找根节点
    }
    return x;
}

合并（Union）

合并操作将两个集合合并。最简单的方法是找到两个集合的根节点，然后将其中一个根节点指向另一个根节点，不考虑树的深度。

void union(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        parent[rootX] = rootY;  // 将一个根节点指向另一个根节点
    }
}

在这个最基础的实现中，合并操作是随意进行的，不考虑树的结构或平衡性。因此，树可能会变得非常深，甚至变成一条链表，这会导致查找操作的效率降低。

算法优化

路径压缩

在查找操作时，通过让节点直接指向根节点，降低树的深度。
路径压缩

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // 路径压缩
    }
    return parent[x];
}

按秩合并

秩可以理解为一个树的深度（高度）。在合并时，可以将秩较小的树合并到秩较大的树上，使树的深度尽量小。因此加入一个 rank 数组记录节点所在树中的高度，用它来控制合并时的平衡性，初始时每个集合的秩都为 1。
按秩合并

控制逻辑如下：

如果 rank[rootX] > rank[rootY]，则令 parent[rootY] = rootX；
如果 rank[rootX] < rank[rootY]，则令 parent[rootX] = rootY；
如果 rank[rootX] == rank[rootY]，则可任意指定根节点，同时将秩的值加 1。

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

代码实现

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

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[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) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
}