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

深入浅出并查集（不相交集合实现思路）

article 2025/2/3 15:13:03

引言

并查集（Disjoint Set Union，简称DSU）是一种用于处理一些不交集的合并及查询问题。它主要支持两种操作：查找（Find）和合并（Union）。

查找：确定某个元素属于哪一个子集。它可以用来确定两个元素是否属于同一子集。
合并：将两个子集合并成一个集合。
由于其实现简单、效率高，并查集被广泛应用于网络连接性问题、图像处理、社交网络分析等多个领域。本文将逐步介绍并查集的基本实现，并探讨其优化方法。

使用场景

并查集广泛应用于以下场景：

连通性问题：判断图中两个节点是否连通。例如，给定一张图，我们可以使用并查集来快速判断图中任意两点是否连通，或者计算整个图有多少个连通分量等。
最小生成树算法：如最小生成树Kruskal算法中用于判断是否形成环。
网络连接问题：判断网络中的两个节点是否连接。
社交网络：判断两个人是否属于同一个社交圈。
图像处理：图像处理中，用于连通区域标记。通过将相邻像素视为元素，并根据它们的颜色或灰度值决定是否合并，可以有效地识别出图像中的各个独立区域。

案例分析

如图所示，0到9的10个数字，每个数字可以表示一个节点，节点之间可以连接起来，成为一个连通分量。我们需要一个数据结构，能够判断两个节点是否属于同一个连通分量（find），同时还可以把两个连通分量连在一起，形成一个更大的连通分量（union）

方案一quick-find

思路分析

我们可以考虑使用Map实现，其中key为节点的值，value为所在连通分量的标识。对于find方法直接使用get即可，而union方法，则需要将两个连通分量的标识统一即可，即找到两个节点的连通分量标识p和q, 将所有value=p的值替换为q(或者q替换为p）

实现步骤如图所示

代码实现

这里使用数组代替map，数组下表对应的节点的值，数组的value为连通分量标识

package uf;

public class UnionFind {
    // 连通分量标识
    private final int[] parent;

    public UnionFind(int size) {
        parent = new int[size];
    }

    private int find(int n) {
        return parent[n];
    }

    private void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        // 更新p的连通分量标识为q
        if (rootP != rootQ) {
            for (int i = 0; i < parent.length; i++) {
                if (parent[i] == rootP) {
                    parent[i] = rootQ;
                }
            }
        }

    }

    public static void main(String[] args) {
        UnionFind uf = new UnionFind(10);
        for (int i = 0; i < uf.parent.length; i++) {
            uf.parent[i] = i;
        }
        uf.union(4, 3);
        int uf4 = uf.find(4);
        int uf3 = uf.find(3);
        int uf8 = uf.find(8);
        System.out.println("uf4的parent: " + uf4 + ", uf3的parent:" + uf3 + ", uf8的parent:" + uf8);
        uf.union(3, 8);
        uf4 = uf.find(4);
        uf3 = uf.find(3);
        uf8 = uf.find(8);
        System.out.println("uf4的parent: " + uf4 + ", uf3的parent:" + uf3 + ", uf8的parent:" + uf8);
    }
}

结果如下

复杂度分析

查找操作（Find）：时间复杂度为O(1)，因为我们直接访问数组中的元素。
合并操作（Union）：时间复杂度为O(n)，因为我们需要遍历整个数组来更新所有属于某个集合的元素。

由于每个节点都指向父节点，这种扁平的结构使得find() 操作的速度显然是很快的，因为它只需要访问 id[] 数组一次, 因此这种算法称为quick-find。但 quick-find 算法一般无法处理大型问题，因为对于每一对输入 union() 都需要扫描整个 id[] 数组。如果把0到9合并为一个连通分量，那么union的复杂度是平方级别的，那么应该如何改进呢？

方案二 quick-union

思路分析

可以这样思考，我们把扁平的结构变成树，每个分量用一棵树表示，树的根节点代表分量的代表元素。查找操作通过不断向上查找父节点，直到找到根节点；合并操作则将一棵树的根节点指向另一棵树的根节点。这样union操作就能避免遍历整个数组了。这种算法叫做quick-union。

代码实现

这里只需要改动find方法和union方法即可，原有的数据结构不用变

private int find(int n) {
        // 根节点的parent指向自己
        while (n != parent[n]) {
            // 不断向上查找父节点
            n = parent[n];
        }
        return n;
    }

    private void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        // 将p的根节点指向q的根节点
        if (rootP != rootQ) {
            parent[rootP] = rootQ;
        }
    }

复杂度分析

quick-union算法的union不用遍历整个数组了，但是算法的复杂度取决于输入的数据，因为构造的树不平衡，

查找操作（Find）：时间复杂度为O(h)，其中h是树的高度。在最坏情况下，树可能退化为链表，h = n，时间复杂度为O(n)。
合并操作（Union）：时间复杂度为O(h)，与查找操作相同。

最坏的情况是变成了一个链表，那么find方法的复杂度变成了O(n)。那么我们该如何改进呢？

方案三加权quick-union

思路分析

为了进一步优化树结构，我们可以引入加权规则：在合并两棵树时，将较小的树合并到较大的树上。这样可以有效减少树的高度，从而降低查找和合并操作的时间复杂度。这种数据结构需要提供一个额外的数组，用于存放根节点对应的连通分量的大小

代码实现

package uf;

public class UnionFind {
    // 父节点
    private final int[] parent;
    // 各个根节点所对应的分量的大小
    private final int[] size;

    public UnionFind(int size) {
        parent = new int[size];
        this.size = new int[size];
    }

    private int find(int n) {
        // 根节点的parent指向自己
        while (n != parent[n]) {
            // 不断向上查找父节点
            n = parent[n];
        }
        return n;
    }

    private void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP != rootQ) {
            // 将分量较大的根节点指向分量较小的根节点
            if (size[p] < size[q]) {
                parent[rootP] = rootQ;
                size[rootQ] += size[rootP];
            } else {
                parent[rootQ] = rootP;
                size[rootP] += size[rootQ];
            }
        }
    }

    public static void main(String[] args) {
        UnionFind uf = new UnionFind(10);
        for (int i = 0; i < uf.parent.length; i++) {
            uf.parent[i] = i;
        }
        uf.union(4, 3);
        int uf4 = uf.find(4);
        int uf3 = uf.find(3);
        int uf8 = uf.find(8);
        System.out.println("uf4的parent: " + uf4 + ", uf3的parent:" + uf3 + ", uf8的parent:" + uf8);
        uf.union(3, 8);
        uf4 = uf.find(4);
        uf3 = uf.find(3);
        uf8 = uf.find(8);
        System.out.println("uf4的parent: " + uf4 + ", uf3的parent:" + uf3 + ", uf8的parent:" + uf8);
    }
}

可以看到结果是将小树的根连到了大树的根上

复杂度分析

查找操作（Find）：时间复杂度为O(log n)，因为加权规则使得树的高度保持在O(log n)级别（这里不做证明，可以参考算法第四版）
合并操作（Union）：时间复杂度为O(log n)，与查找操作相同。

加权树实现显著提高了并查集的效率，尤其是在处理大规模数据时。但是能不能让find方法的复杂度像quick-find一样快呢？

方案四路径压缩

思路分析

我们尝试结合quick-find的扁平的数据结构，以及加权quick-union的平衡树的结构。在find方法中，在节点向上查询的过程中，顺便将路径中的节点的父节点指向root，这种操作叫做路径压缩。这样后续的find操作，对于压缩过路径的连通分量来说，可以使得树更扁平，提高find的效率。

假设我们有如下树结构

1
| \
2 3
\
4

当我们调用 find(4) 时，路径压缩会将节点 4、3、2 直接指向根节点 1。
压缩后的树结构变为：

          1
        /  |  \
      2 3 4

代码实现

这里是需要修改find方法，递归地修改每个父节点的parent

    private int find(int n) {
        while (n != parent[n]) {
            // 递归地将路径上的所有节点指向根节点
            parent[n]= find(parent[n]);
        }
        return n;
    }