算法之并查集（Union-Find）：连通世界的动态维护艺术

紫风

发布于 2025-10-14 15:14:22

1600

一、算法本质

并查集如同社交网络的关系管家：

家族管理：每个元素属于一个集合（家族），初始自立门户
认祖归宗：通过union操作合并两个家族（家族联姻）
寻根问祖：通过find操作追溯最终祖先（确认家族归属）
路径压缩：优化家族关系树（扁平化管理）

整个过程像动态维护社交圈：随时合并圈子，快速确认两人是否属于同一群体。

二、Java实现（路径压缩+按秩合并优化版）

class UnionFind {
    private int[] parent;  // 父节点数组
    private int[] rank;    // 秩（树高）

    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; 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) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX] += 1; // 树高增加
            }
        }
    }

    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }

    public static void main(String[] args) {
        UnionFind uf = new UnionFind(5);
        uf.union(0, 1);
        uf.union(2, 3);
        System.out.println(uf.isConnected(0, 1)); // true
        System.out.println(uf.isConnected(1, 2)); // false
        uf.union(1, 3);
        System.out.println(uf.isConnected(0, 3)); // true
    }
}

三、性能分析

指标	数值	说明
时间复杂度	O(α(n)) ≈ O(1)	α为阿克曼函数的反函数，增长极慢
空间复杂度	O(n)	存储父节点和秩数组
特殊能力	动态连通性维护	支持实时合并和查询

优化精髓：

路径压缩：查询时压平访问路径，缩短后续查询时间
按秩合并：小树合并到大树，控制树的高度增长

四、应用场景

社交网络：实时判断用户关系（是否好友）
游戏开发：迷宫连通性检测/像素区域合并
电路设计：元件连通性验证
图像处理：连通区域标记
动态图：Kruskal最小生成树算法

典型案例：

Facebook好友关系链实时更新
《我的世界》方块连通区域检测
电网故障时的连通区域分析
医学影像的肿瘤区域标记

五、学习路线

新手必练：

手动画出合并过程（树结构演变）
实现基础版本→添加路径压缩→加入按秩合并
解决LeetCode 547（省份数量问题）

// LeetCode 547省份数量解法核心
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();
}

高手进阶：

实现动态并查集（支持插入新元素）
开发带权并查集（记录集合附加信息）
研究并行化并查集（多线程合并优化）

// 带权并查集示例（记录集合大小）
class WeightedUnionFind {
    private int[] size; // 新增大小数组
    
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (size[rootX] < size[rootY]) {
                parent[rootX] = rootY;
                size[rootY] += size[rootX];
            } else {
                parent[rootY] = rootX;
                size[rootX] += size[rootY];
            }
        }
    }
}