每日算法 — 使用java实现并查集：路径压缩与按秩合并

并查集（Disjoint Set Union，DSU）是一种高效处理元素分组与合并问题的数据结构。它支持两种核心操作：查找（Find）某个元素所属的集合，以及合并（Union）两个集合。凭借路径压缩与按秩合并两大优化策略，并查集的时间复杂度接近常数级，是图论中判断连通性、生成最小生成树（Kruskal算法）以及社交网络分析的核心工具。本文将用 Java 从零实现一个完整的并查集，并深入讲解两种优化策略的原理与效果。

一、为什么需要并查集

想象一个社交网络平台，用户之间可以添加好友关系。系统需要快速回答以下问题：

• 用户 A 和用户 B 是否属于同一个朋友圈？
• 将用户 C 和用户 D 的朋友圈合并为一个整体。

如果用暴力方法维护邻接表并每次执行 BFS/DFS 判断连通性，时间复杂度为 O(V+E)。而并查集可以在近乎 O(1) 的时间内完成查询与合并。

其中 α(n) 是阿克曼函数的反函数，增长极其缓慢，对于任何实际数据规模都小于 5。

二、核心思想：用树表示集合

并查集的核心思想是：每个集合用一棵树表示，树的根节点作为该集合的唯一标识。每个节点只需记录其父节点，根节点的父节点指向自身。

2.1 数组表示法

使用一个整型数组 parent[] 即可实现：

• parent[i] = i：表示 i 是根节点（集合代表）
• parent[i] = j：表示 i 的父节点是 j

/**
 * 并查集基础结构
 * 使用一维数组 parent 记录每个节点的父节点
 */
public class UnionFind {
    private int[] parent;   // parent[i] 表示节点 i 的父节点
    private int count;      // 当前连通分量的数量

    /**
     * 初始化并查集，每个节点自成一个集合
     * @param n 节点总数（编号 0 ~ n-1）
     */
    public UnionFind(int n) {
        parent = new int[n];
        count = n;
        // 初始时，每个节点的父节点都是自己
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
}

三、基础操作：Find 与 Union

3.1 查找操作（Find）

查找某个元素所属集合的根节点。通过不断向上追溯父节点，直到找到父节点指向自身的根节点。

/**
 * 查找节点 x 所属集合的根节点（代表元素）
 * 时间复杂度：O(h)，h 为树的高度
 * @param x 待查找的节点
 * @return 根节点编号
 */
public int find(int x) {
    // 如果父节点不是自己，继续向上查找
    while (parent[x] != x) {
        x = parent[x];
    }
    return x;
}

3.2 合并操作（Union）

将两个元素所在的集合合并。先分别找到两个元素的根节点，然后将其中一个根节点的父节点指向另一个根节点。

/**
 * 合并节点 x 和节点 y 所在的集合
 * 时间复杂度：O(h)
 * @param x 第一个节点
 * @param y 第二个节点
 */
public void union(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    // 如果已经在同一个集合，无需合并
    if (rootX == rootY) return;
    // 将 rootX 的根指向 rootY
    parent[rootX] = rootY;
    count--; // 连通分量减少一个
}

3.3 判断是否连通

/**
 * 判断节点 x 和节点 y 是否在同一个集合中
 * @return true 表示连通，false 表示不连通
 */
public boolean connected(int x, int y) {
    return find(x) == find(y);
}

/**
 * 获取当前连通分量的数量
 */
public int getCount() {
    return count;
}

四、优化策略一：路径压缩（Path Compression）

4.1 问题分析

基础版本的 Union 操作可能产生退化的树结构。例如，每次都把一棵树的根接到另一棵树的根上，如果操作不当，树的高度可能达到 O(n)，导致 Find 操作退化。

4.2 路径压缩原理

路径压缩的核心思想是：在 Find 操作中，将查找路径上的所有节点直接挂到根节点下。这样下次再访问这些节点时，只需一步即可到达根节点。

/**
 * 查找并压缩路径
 * 递归版本：在返回过程中，将路径上每个节点的父节点直接设为根节点
 * 时间复杂度：O(α(n))
 * @param x 待查找的节点
 * @return 根节点编号
 */
public int find(int x) {
    if (parent[x] != x) {
        // 递归查找根节点，并将当前节点的父节点直接指向根节点
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

4.3 路径压缩效果

路径压缩使树的高度急剧降低。经过多次查询后，几乎所有节点都会直接连接到根节点，形成扁平化的星形结构，大幅提升后续操作效率。

五、优化策略二：按秩合并（Union by Rank）

5.1 问题分析

即使有了路径压缩，如果合并时总是随意选择根节点，仍然可能产生较高的树。理想情况是将较矮的树合并到较高的树下，以控制整体高度。

5.2 按秩合并原理

为每棵树维护一个秩（rank），表示树的高度的上界。合并时，总是将秩较小的树的根节点挂到秩较大的树的根节点下。

• 如果两棵树秩不同：秩小的挂到秩大的下面，合并后秩不变
• 如果两棵树秩相同：任选一棵作为根，其秩加 1

public class UnionFind {
    private int[] parent;   // 父节点数组
    private int[] rank;     // rank[i] 表示以 i 为根的树的高度上界
    private int count;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        count = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1; // 初始时每棵树只有一个节点，高度为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) return;

        // 将秩较小的树挂到秩较大的树下
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            // 秩相等时，任选一棵作为根，秩加1
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        count--;
    }
}

六、完整Java实现

以下是集成了路径压缩与按秩合并的完整并查集实现，包含一个实际应用场景：判断无向图中的连通分量数量。

/**
 * 并查集完整实现（Java）
 * 支持：路径压缩、按秩合并、连通性查询、连通分量统计
 * 时间复杂度：O(α(n))，α 为阿克曼函数反函数
 */
public class UnionFind {

    // ==================== 成员变量 ====================
    private int[] parent;   // 父节点数组
    private int[] rank;     // 秩数组，表示树高的上界
    private int count;      // 当前连通分量数量

    // ==================== 构造函数 ====================
    /**
     * 初始化并查集
     * @param n 元素个数，编号从 0 到 n-1
     */
    public UnionFind(int n) {
        if (n <= 0) {
            throw new IllegalArgumentException("元素数量必须大于0");
        }
        parent = new int[n];
        rank = new int[n];
        count = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;  // 每个元素初始时父节点指向自己
            rank[i] = 1;    // 初始秩为1（单个节点）
        }
    }

    // ==================== 核心操作 ====================
    /**
     * 查找元素 x 所属集合的根节点
     * 同时执行路径压缩，将 x 到根路径上的所有节点直接挂到根下
     * @param x 待查找元素
     * @return 根节点编号
     */
    public int find(int x) {
        if (x < 0 || x >= parent.length) {
            throw new IllegalArgumentException("元素编号越界");
        }
        // 递归路径压缩
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    /**
     * 合并元素 x 和元素 y 所在的集合
     * 使用按秩合并策略，将矮树合并到高树下
     * @param x 第一个元素
     * @param y 第二个元素
     */
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        // 已在同一集合，无需合并
        if (rootX == rootY) {
            return;
        }

        // 按秩合并：矮树挂到高树下
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            // 秩相等时，rootX 作为新根，秩加1
            parent[rootY] = rootX;
            rank[rootX]++;
        }

        count--; // 合并后连通分量减1
    }

    /**
     * 判断元素 x 和元素 y 是否在同一个集合中
     * @return true 表示连通，false 表示不连通
     */
    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }

    /**
     * 获取当前连通分量的数量
     */
    public int getCount() {
        return count;
    }

    /**
     * 获取指定集合的大小（遍历查找，效率较低，仅用于调试）
     * @param root 集合根节点
     * @return 集合中元素数量
     */
    public int getSetSize(int root) {
        int size = 0;
        for (int i = 0; i < parent.length; i++) {
            if (find(i) == root) {
                size++;
            }
        }
        return size;
    }

    // ==================== 测试主程序 ====================
    public static void main(String[] args) {
        // 场景：10个用户，逐步建立好友关系，观察朋友圈变化
        int n = 10;
        UnionFind uf = new UnionFind(n);

        System.out.println("初始状态：" + uf.getCount() + " 个连通分量");

        // 建立好友关系（合并集合）
        int[][] friendships = {
            {0, 1}, {1, 2}, {3, 4}, {5, 6}, {6, 7}, {8, 9},
            {2, 3}, {7, 8}
        };

        System.out.println("\n逐步合并好友关系：");
        for (int[] f : friendships) {
            int a = f[0], b = f[1];
            boolean wasConnected = uf.connected(a, b);
            uf.union(a, b);
            System.out.printf("  合并 %d 和 %d: 之前%s连通, 剩余 %d 个朋友圈%n",
                a, b, wasConnected ? "已" : "未", uf.getCount());
        }

        // 查询连通性
        System.out.println("\n连通性查询结果：");
        System.out.println("  0 和 4 是否连通？" + uf.connected(0, 4));
        System.out.println("  0 和 9 是否连通？" + uf.connected(0, 9));
        System.out.println("  5 和 9 是否连通？" + uf.connected(5, 9));

        // 最终状态
        System.out.println("\n最终连通分量数量：" + uf.getCount());

        // 验证路径压缩效果：再次查询时parent数组已被扁平化
        System.out.println("\n路径压缩后，各节点根节点：");
        for (int i = 0; i < n; i++) {
            System.out.printf("  节点 %d -> 根节点 %d%n", i, uf.find(i));
        }
    }
}

七、应用场景：朋友圈合并问题

LeetCode 经典题目 547. 省份数量 是并查集的典型应用。给定一个 n×n 的矩阵 isConnected，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，求省份（连通分量）的总数。

/**
 * 使用并查集解决省份数量问题
 * @param isConnected 邻接矩阵
 * @return 省份数量
 */
public int findCircleNum(int[][] isConnected) {
    int n = isConnected.length;
    UnionFind uf = new UnionFind(n);

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (isConnected[i][j] == 1) {
                uf.union(i, j);
            }
        }
    }

    return uf.getCount();
}

八、复杂度分析

其中 α(n) 是阿克曼函数的反函数，在宇宙原子数量级别的数据范围内，其值不超过 4。因此并查集的操作可以视为均摊常数时间。

九、总结

并查集以其简洁的结构和惊人的效率，成为处理动态连通性问题的首选数据结构。通过本文的学习，你掌握了：

1. 数组表示法：用父节点数组高效表示森林结构
2. 路径压缩：在查找时将节点直接挂到根下，扁平化树结构
3. 按秩合并：合并时矮树挂高树，控制树高增长
4. 实际应用：连通分量统计、Kruskal最小生成树、社交网络分析等

这两种优化策略可以单独使用，也可以同时使用。实际应用中，路径压缩 + 按秩合并的组合是最优配置，能够在理论和实践中都达到近乎常数的时间复杂度。