Java并查集实现：原理、代码与连通块应用

凌晨两点半

发布时间：2026-10-16| 4人浏览过

原创

本文详细介绍并查集（Disjoint Set Union）在Java中的实现。通过路径压缩优化查询效率，讲解核心函数的逻辑，并结合网络拓扑等实际场景，演示如何利用该结构快速统计连通区域个数。

第1步：理解并查集核心逻辑

并查集是一种树型数据结构，用于处理不相交集合的合并及查询问题。其核心操作包含两个部分：

查询（Find/GetFather）：确定元素属于哪个集合，即找到元素所在树的根节点。
合并（Union/Join）：将两个不同的集合合并为一个集合。

在实际应用中，如果涉及多次跨集合查询，使用并查集可以显著降低时间复杂度，避免重复遍历。

获取根节点与路径压缩

为了优化查询速度，通常采用路径压缩策略。在寻找根节点的过程中，直接将沿途经过的节点的父指针指向根节点，从而扁平化树结构。


public static Integer getFather(int[] father, int u) {
    if (father[u] != u) {
        // 递归查找父节点，并将当前节点u直接指向找到的根节点
        father[u] = getFather(father, father[u]);
    }
    return father[u];
}

逻辑说明：若father[u]等于u，说明已到达根节点；否则递归调用并更新路径，确保下次查询时直接从子节点指向根节点，极大提升后续性能。

合并两个集合

合并操作的思路是找出两个元素的根节点，若根节点不同，则将其中一个根节点的父节点指向另一个根节点，从而实现集合合并。


public static void join(int[] father, int x, int y) {
    int fx = getFather(father, x);
    int fy = getFather(father, y);
    if (fx != fy) {
        father[fx] = fy;
    }
}

关键参数：
- father：存储每个节点父节点的数组。
- x, y：需要合并的两个节点索引。
- 完成状态：执行后，x和y所在的集合将共享同一个根节点fy。

第2步：完整代码验证过程

通过初始化独立集合并逐步合并，观察集合关系的变化。以下示例使用10个节点（0-9）演示合并过程。


public static void main(String[] args) {
    int n = 10;
    int[] a = new int[n];
    
    // 1. 初始化：每个元素自成一个集合
    for (int i = 0; i < n; i++) {
        a[i] = i;
    }
    
    // 打印初始状态
    for (int i = 0; i < n; i++) {
        System.out.println(i + " -> 根节点: " + getFather(a, i));
    }
    
    System.out.println("-------------------------");
    
    // 2. 合并 0 和 1
    join(a, 0, 1); 
    printState(a, n);
    
    // 3. 合并 2 和 3
    join(a, 2, 3); 
    printState(a, n);
    
    // 4. 合并 1 和 3（间接合并了0,1,2,3）
    join(a, 1, 3); 
    printState(a, n);
}

// 辅助方法：打印当前所有节点的根节点状态
private static void printState(int[] father, int n) {
    for (int i = 0; i < n; i++) {
        System.out.println(i + " -> 根节点: " + getFather(father, i));
    }
}