一、项目背景详细介绍

在计算机科学中，并查集（Union–Find） 又称作不相交集（Disjoint Set），是一种树形的数据结构，主要用于处理一些不相交集合的合并及查询问题。它支持两种主要操作：

1. 查找（Find）：确定元素所属的集合标识（通常返回元素所在集合的“根”）。

2. 合并（Union）：将两个集合合并成一个集合。

并查集因其近乎常数级别的时间复杂度（反 α(n)，其中 α 为阿克曼函数的反函数）广泛应用于网络连通性、最小生成树（Kruskal 算法）等场景。在大数据量的情况下，其效率远高于朴素的图遍历方法。

本文旨在使用 Java 语言实现一套通用的并查集算法，支持按秩合并（Union by Rank）和路径压缩（Path Compression）优化，并统计各操作的平均执行成本，帮助读者深入理解并查集的原理与优化思路。

---

二、项目需求详细介绍

1. 核心功能

   • 提供并查集的初始化、查找（find）与合并（union）操作。

   • 支持 int 类型元素，也可通过映射扩展到任意自定义对象。

2. 性能优化

   • 实现按秩合并（Union by Rank）或按大小合并（Union by Size）。

   • 实现路径压缩（Path Compression），在查找时将节点直接挂到根节点。

3. 性能统计

   • 统计每次 find 和 union 操作的平均递归深度或循环次数，辅助性能评估。

4. 代码结构

   • 工具类 UnionFind：包含初始化、查找、合并、统计接口；

   • 演示类 UnionFindDemo：构造示例数据，调用并查集方法并打印结果；

   • 单元测试类 UnionFindTest：使用 JUnit 测试各功能正确性和优化效果。

5. 文档与注释

   • 所有代码需详细注释，说明核心逻辑与优化手段；

   • 博客文章正文需不少于 5000 字（仅汉字计数），按照目录结构撰写，面向教学和学习用途。

6. 可扩展性

   • 后续可基于此并查集实现应用：动态连通性检测、社交网络朋友圈合并、Kruskal 最小生成树等。

---

三、相关技术详细介绍

1. 数组与映射

   • 并查集常用数组 parent[] 存储父节点，rank[] 或 size[] 存储秩或子树大小；

   • 若需要支持任意对象，可通过 Map<T, Integer> 将对象映射到数组索引。

2. 按秩合并（Union by Rank）

   • 每个集合附带一个“秩”（树的高度近似值），合并时将低秩树挂到高秩树下，避免树过高。

   • 当秩相等时，任选一方作为新根，并将其秩加 1。

3. 路径压缩（Path Compression）

   • 在执行 find 时，通过递归或循环将沿途访问节点直接挂到根节点上，极大减少后续查找的路径长度。

   • 常见写法：

if (parent[x] != x) {
    parent[x] = find(parent[x]);
}
return parent[x];

1. 时间复杂度分析

   • 经过以上两种优化后，单次操作摊销复杂度趋近于 O(α(n))，几乎可视为常数。

   • 阿克曼函数的反函数 α(n) 在任何可见宇宙尺度下都不超过 5。

2. JUnit 单元测试

   • 使用 JUnit 5 为各操作编写测试用例，验证并查集在各种合并与查找场景下的正确性。

---

四、实现思路详细介绍

1. 数据结构初始化

   • 构造方法接收元素总数 n，创建 parent 与 rank（或 size）长度为 n 的数组；

   • 初始时 parent[i] = i，rank[i] = 1（或 size[i] = 1）。

2. 查找操作 find(x)

   • 递归实现：若 parent[x] != x，则 parent[x] = find(parent[x])，并返回新父节点；否则直接返回 x；

   • 可统计递归深度或路径压缩步骤数。

3. 合并操作 union(x, y)

   • 分别查找 x、y 的根 rootX、rootY；若相同则直接返回；

   • 比较 rank[rootX] 与 rank[rootY]：将低秩根指向高秩根；

   • 若相等则任选一方作为新根，并 rank[新根]++；

   • 统计一次合并操作调用。

4. 统计接口

   • 维护 operationCount、totalFindDepth 等字段；

   • 在 find 和 union 内适时累加，后续提供平均深度等统计信息。

5. 示例演示

   • 构造若干随机或手动连边操作，验证连通性查询结果与统计数据；

   • 通过打印展示树高趋势、路径浓缩效果等。

---

五、完整实现代码

// 文件：UnionFind.java
package com.example.unionfind;

import java.util.Arrays;

/**
 * UnionFind：并查集（不相交集）数据结构
 * 支持按秩合并和路径压缩，并提供操作统计
 */
public class UnionFind {
    // parent[i] 表示第 i 个节点的父节点
    private int[] parent;
    // rank[i] 表示以 i 为根的树的“秩”（近似高度）
    private int[] rank;
    // 操作统计
    private long findCount = 0;       // find 操作次数
    private long unionCount = 0;      // union 操作次数
    private long totalFindPath = 0;   // find 总路径压缩次数

    /**
     * 构造并查集，初始化 0..n-1 共 n 个元素
     * @param n 元素数量
     */
    public UnionFind(int n) {
        if (n <= 0) {
            throw new IllegalArgumentException("元素数量必须大于 0");
        }
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;     // 初始时每个节点都是自己的父节点
            rank[i] = 1;       // 初始秩为 1
        }
    }

    /**
     * 查找操作：查找元素 x 所在集合的根节点，并进行路径压缩
     * @param x 要查找的元素索引
     * @return 根节点索引
     */
    public int find(int x) {
        findCount++;
        if (x < 0 || x >= parent.length) {
            throw new IllegalArgumentException("元素索引越界");
        }
        // 递归路径压缩
        if (parent[x] != x) {
            int originalParent = parent[x];
            parent[x] = find(originalParent);
            totalFindPath++;
        }
        return parent[x];
    }

    /**
     * 合并操作：将元素 x 和 y 所在集合合并在一起
     * @param x 元素 x 索引
     * @param y 元素 y 索引
     * @return 合并成功返回 true；若已在同一集合则返回 false
     */
    public boolean union(int x, int y) {
        unionCount++;
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return false;  // 已在同一集合
        }
        // 按秩合并：低秩根挂到高秩根下
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            // 秩相同，任选一方并秩+1
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        return true;
    }

    /**
     * 判断元素 x 和 y 是否连通（在同一个集合）
     * @param x 元素 x 索引
     * @param y 元素 y 索引
     * @return 若同根则连通，返回 true；否则 false
     */
    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }

    /** 获取 find 操作总次数 */
    public long getFindCount() {
        return findCount;
    }

    /** 获取 union 操作总次数 */
    public long getUnionCount() {
        return unionCount;
    }

    /** 获取 find 操作的总路径压缩次数 */
    public long getTotalFindPath() {
        return totalFindPath;
    }

    /**
     * 打印当前 parent 数组状态
     */
    public void printParents() {
        System.out.println("parent: " + Arrays.toString(parent));
    }

    /**
     * 打印当前 rank 数组状态
     */
    public void printRanks() {
        System.out.println("rank:   " + Arrays.toString(rank));
    }
}

// 文件：UnionFindDemo.java
package com.example.unionfind;

public class UnionFindDemo {
    public static void main(String[] args) {
        int n = 10;
        UnionFind uf = new UnionFind(n);

        // 演示若干 union 操作
        uf.union(1, 2);
        uf.union(2, 5);
        uf.union(5, 6);
        uf.union(6, 7);
        uf.union(3, 8);
        uf.union(8, 9);

        System.out.println("合并操作后：");
        uf.printParents();
        uf.printRanks();

        // 演示连通性查询
        System.out.printf("1 和 7 连通？%b%n", uf.connected(1, 7));  // true
        System.out.printf("1 和 3 连通？%b%n", uf.connected(1, 3));  // false

        // 更多合并，测试路径压缩效果
        uf.union(7, 3);
        System.out.println("再次合并 7 和 3 后：");
        uf.printParents();

        // 输出统计信息
        System.out.printf("find 调用总次数：%d%n", uf.getFindCount());
        System.out.printf("union 调用总次数：%d%n", uf.getUnionCount());
        System.out.printf("路径压缩总次数：%d%n", uf.getTotalFindPath());
    }
}

// 文件：UnionFindTest.java
package com.example.unionfind;

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;

public class UnionFindTest {

    @Test
    public void testInitialization() {
        UnionFind uf = new UnionFind(5);
        for (int i = 0; i < 5; i++) {
            assertEquals(i, uf.find(i));
        }
    }

    @Test
    public void testUnionAndConnected() {
        UnionFind uf = new UnionFind(5);
        assertFalse(uf.connected(0, 1));
        uf.union(0, 1);
        assertTrue(uf.connected(0, 1));
    }

    @Test
    public void testMultipleUnions() {
        UnionFind uf = new UnionFind(6);
        uf.union(0, 1);
        uf.union(2, 3);
        uf.union(1, 2);
        assertTrue(uf.connected(0, 3));
        assertFalse(uf.connected(0, 4));
    }

    @Test
    public void testPathCompressionEffect() {
        UnionFind uf = new UnionFind(4);
        uf.union(0,1);
        uf.union(1,2);
        uf.find(2);
        // after path compression, parent[2] should point directly to 0
        assertEquals(uf.find(2), uf.find(0));
    }

    @Test
    public void testInvalidInitialization() {
        assertThrows(IllegalArgumentException.class, () -> new UnionFind(0));
    }

    @Test
    public void testIndexOutOfBounds() {
        UnionFind uf = new UnionFind(3);
        assertThrows(IllegalArgumentException.class, () -> uf.find(5));
    }
}

六、代码详细解读

1. 构造方法

   • 初始化 parent 数组，使每个元素自成一组；

   • 初始化 rank 数组，所有秩均设为 1；

   • 校验参数合法性，避免 n <= 0 的异常场景。

2. find 方法

   • 递增 findCount 统计调用次数；

   • 边界检查，防止索引越界；

   • 通过递归方式实现路径压缩，将 parent[x] 指向根节点，并在压缩时累加 totalFindPath；

   • 返回根节点索引。

3. union 方法

   • 递增 unionCount 统计调用次数；

   • 分别调用 find 得到两个元素的根；

   • 若根相同，说明已连通，无需合并；

   • 比较两根的 rank，实现按秩合并；

   • 若秩相等，则将其中一个根的 rank 自增 1；

4. connected 方法

   • 通过比较两元素的根是否相等，判断连通性。

5. 统计与打印方法

   • getFindCount、getUnionCount、getTotalFindPath 分别返回对应统计值；

   • printParents 与 printRanks 打印当前数组状态，方便观察结构变化。

---

七、项目详细总结

本文使用 Java 语言完整实现了并查集（Union–Find）算法，并引入按秩合并与路径压缩两种经典优化手段，使得在大规模操作下，单次查询和合并均可接近常数时间。通过统计接口，我们可以直观地观察到路径压缩带来的性能提升。JUnit 测试用例则保证了算法在各种边界条件下的正确性与健壮性。本项目不仅是一份可直接引用的工具库，也可作为学习并查集原理和优化技巧的示例代码。

---

八、项目常见问题及解答

1. 问：什么是“秩”？
   答：“秩”是树的近似高度度量，用于指导合并时优先将矮树挂到高树下，防止树过深。

2. 问：路径压缩是怎么工作的？
   答：在 find 过程中，递归返回根节点时，将当前节点的父指针直接指向根节点，从而降低树的高度。

3. 问：为什么要同时使用按秩合并和路径压缩？
   答：这两种优化手段互补：按秩合并防止树初始过深，路径压缩在运行中持续优化树高度，二者结合效果最佳。

4. 问：并查集能否支持删除元素？
   答：标准并查集不支持高效删除，可通过打标记或重建结构来实现“删除”。

5. 问：如何将并查集应用于自定义对象？
   答：可用 Map<T, Integer> 将对象映射到数组索引，再使用相同逻辑操作索引。

---

九、扩展方向与性能优化

1. 按大小合并（Union by Size）

   • 用子树大小 size[] 代替秩 rank[]，将小树挂到大树下。

2. 非递归路径压缩

   • 使用循环两次遍历路径，先找到根再重新遍历路径压缩，减少递归开销。

3. 并发并查集

   • 在多线程场景下，添加锁或使用无锁方案，实现线程安全的并查集。

4. 应用场景

   • 最小生成树：Kruskal 算法中快速检测边是否形成环；

   • 网络连通性：动态判断节点连通或分裂；

   • 社交网络：群组合并与查询。

5. 性能基准测试

   • 对比不同优化组合（无优化、单独按秩、单独路径压缩、双重优化）在大规模随机数据上的耗时和操作计数，形成可视化报表，帮助选择最佳实现策略。