Java不相交集合详解（手把手教你实现并查集 Union-Find 数据结构）

应用场景

不相交集合广泛应用于以下场景：

• 判断图中两点是否连通（如社交网络中的好友关系）
• Kruskal 最小生成树算法
• 图像处理中的区域合并
• 动态连通性问题（如网络连接状态）

Java 实现不相交集合（基础版）

我们首先用数组来实现一个简单的不相交集合。每个元素的父节点存储在数组中，初始时每个元素都是自己的父节点。

public class DisjointSet {    private int[] parent;    // 构造函数：初始化 n 个元素    public DisjointSet(int n) {        parent = new int[n];        for (int i = 0; i < n; i++) {            parent[i] = i; // 每个元素初始时是自己的根        }    }    // 查找 x 所在集合的根    public int find(int x) {        if (parent[x] != x) {            return find(parent[x]);        }        return x;    }    // 合并 x 和 y 所在的集合    public void union(int x, int y) {        int rootX = find(x);        int rootY = find(y);        if (rootX != rootY) {            parent[rootX] = rootY;        }    }}

优化：路径压缩 + 按秩合并

上面的基础版本在最坏情况下效率较低。我们可以使用两种经典优化技术：

1. 路径压缩（Path Compression）：在 find 操作时，将路径上的所有节点直接指向根节点，减少后续查找时间。
2. 按秩合并（Union by Rank）：在 union 操作时，总是将较小的树合并到较大的树下，避免树过高。

下面是优化后的完整 Java 实现：

public class OptimizedDisjointSet {    private int[] parent;    private int[] rank; // 用于记录树的高度（秩）    public OptimizedDisjointSet(int n) {        parent = new int[n];        rank = new int[n];        for (int i = 0; i < n; i++) {            parent[i] = i;            rank[i] = 0;        }    }    // 带路径压缩的 find    public int find(int x) {        if (parent[x] != x) {            parent[x] = find(parent[x]); // 路径压缩        }        return parent[x];    }    // 带按秩合并的 union    public void union(int x, int y) {        int rootX = find(x);        int rootY = find(y);        if (rootX != rootY) {            if (rank[rootX] < rank[rootY]) {                parent[rootX] = rootY;            } else if (rank[rootX] > rank[rootY]) {                parent[rootY] = rootX;            } else {                parent[rootY] = rootX;                rank[rootX]++;            }        }    }}

使用示例

下面是一个简单的使用示例，演示如何判断两个节点是否连通：

public class Main {    public static void main(String[] args) {        OptimizedDisjointSet ds = new OptimizedDisjointSet(5);        ds.union(0, 1);        ds.union(2, 3);        ds.union(1, 2);        // 检查 0 和 3 是否连通        if (ds.find(0) == ds.find(3)) {            System.out.println("0 和 3 在同一个集合中");        } else {            System.out.println("0 和 3 不在同一个集合中");        }    }}

总结

通过本教程，你已经掌握了 Java不相交集合 的基本原理和实现方法。结合 路径压缩 与 按秩合并，并查集的操作接近常数时间复杂度（阿克曼函数的反函数），效率极高。

无论是准备面试、刷 LeetCode，还是开发实际项目，Union-Find数据结构 都是你工具箱中不可或缺的利器。快动手试试吧！

关键词回顾：Java不相交集合、并查集教程、Union-Find数据结构、Java实现并查集