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

引言

并查集（Union-Find），又称不相交集合（Disjoint Set Union, DSU），是一种用于管理元素分组的高效数据结构。它支持两种核心操作：查找（Find）某个元素所属的集合，以及合并（Union）两个集合。借助路径压缩和按秩合并两种优化策略，并查集的均摊时间复杂度可接近常数级别 $O(\alpha(n))$，其中 $\alpha$ 为阿克曼函数的反函数。

应用场景

并查集广泛应用于图论算法中：判断无向图的连通分量、检测环、Kruskal最小生成树算法中的边选择、以及社交网络中的好友圈子分析等场景。

基础实现

public class UnionFind {
    private int[] parent; // parent[i]表示i的父节点
    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;
        }
    }

    // 查找元素x所属的根节点（基础版本，无优化）
    public int findBasic(int x) {
        while (parent[x] != x) {
            x = parent[x];
        }
        return x;
    }
}

路径压缩优化

路径压缩在查找过程中将访问路径上的所有节点直接连接到根节点，扁平化树结构，大幅降低后续查找的深度。

    // 路径压缩版本：递归实现
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 递归压缩路径
        }
        return parent[x];
    }

    // 路径压缩版本：迭代实现（更省栈空间）
    public int findIterative(int x) {
        int root = x;
        while (parent[root] != root) {
            root = parent[root];
        }
        // 第二次遍历，压缩路径
        while (parent[x] != x) {
            int next = parent[x];
            parent[x] = root;
            x = next;
        }
        return root;
    }

按秩合并优化

按秩合并策略在合并两个集合时，总是将秩较小的树连接到秩较大的树下，避免树高过度增长。

    // 合并元素x和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 {
            // 秩相等时，任选一个作为根，并将其秩+1
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        count--; // 连通分量减少
    }

    // 判断x和y是否连通
    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }

    public int getCount() {
        return count;
    }

完整测试用例：检测无向图中的环

public class UnionFindCycleDetection {

    static class Edge {
        int u, v;
        Edge(int u, int v) { this.u = u; this.v = v; }
    }

    // 使用并查集检测无向图是否存在环
    public static boolean hasCycle(int n, Edge[] edges) {
        UnionFind uf = new UnionFind(n);

        for (Edge e : edges) {
            if (uf.connected(e.u, e.v)) {
                // 两个端点已在同一集合，添加此边会形成环
                return true;
            }
            uf.union(e.u, e.v);
        }
        return false;
    }

    public static void main(String[] args) {
        // 测试图：3个节点，3条边构成三角形
        Edge[] edges = { new Edge(0, 1), new Edge(1, 2), new Edge(0, 2) };
        System.out.println("Has cycle: " + hasCycle(3, edges)); // true

        // 测试图：树结构，无环
        Edge[] treeEdges = { new Edge(0, 1), new Edge(1, 2), new Edge(1, 3) };
        System.out.println("Has cycle: " + hasCycle(4, treeEdges)); // false
    }
}

Kruskal最小生成树中的应用

import java.util.*;

public class KruskalMST {

    static class Edge implements Comparable<Edge> {
        int u, v, weight;
        Edge(int u, int v, int w) { this.u = u; this.v = v; this.weight = w; }
        public int compareTo(Edge o) { return this.weight - o.weight; }
    }

    public static List<Edge> kruskal(int n, List<Edge> edges) {
        Collections.sort(edges); // 按权重升序排序
        UnionFind uf = new UnionFind(n);
        List<Edge> mst = new ArrayList<>();

        for (Edge e : edges) {
            if (!uf.connected(e.u, e.v)) {
                uf.union(e.u, e.v);
                mst.add(e);
                if (mst.size() == n - 1) break; // 已选n-1条边
            }
        }
        return mst;
    }
}

复杂度分析

路径压缩与按秩合并的结合使并查集成为处理动态连通性问题的最优数据结构，在实际工程中几乎达到常数时间效率。