并查集基础（长文解析）

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

• 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;
• 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 82w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 2900+ 小伙伴加入学习 ，欢迎点击围观

并查集基础概述

在编程与算法领域，并查集（Union-Find Set）是一种基础但极其实用的数据结构。它能够高效地解决动态连通性问题，例如判断两个元素是否属于同一集合，或者合并两个不相交的集合。对于编程初学者而言，并查集的学习曲线相对平缓，但其背后的优化思想（如路径压缩、按秩合并）却蕴含着深刻的算法设计理念。本文将从零开始讲解并查集的核心概念、实现方法及应用场景，帮助读者建立清晰的理解框架。

一、并查集的基本概念

1.1 连通性问题：以社团为例

想象一个学校有多个社团，每个社团由若干成员组成。我们需要快速回答以下两类问题：

• 查询：两个成员是否属于同一社团？
• 合并：当两个社团合并时，如何快速更新数据？

并查集正是为这类问题设计的解决方案。其核心目标是维护动态变化的集合关系，支持高效查询和合并操作。

1.2 核心操作定义

并查集主要包含以下三种操作：

• 初始化：为每个元素单独建立一个集合。
• 查找（Find）：确定某个元素所属的集合根节点。
• 合并（Union）：将两个元素所在的集合合并为一个集合。

1.3 父节点数组：实现的基石

并查集通常通过一个父节点数组 parent 来实现。数组的索引代表元素，而 parent[i] 表示该元素的父节点。初始时，每个元素的父节点指向自身，形成独立的集合。

例如，假设元素为 0,1,2,3，则初始状态为：

parent = [0, 1, 2, 3]

二、并查集的核心操作实现

2.1 查找（Find）操作：寻找根节点

查找操作的目标是确定某个元素的根节点。根节点的特征是其父节点指向自身。例如，查找元素 2 的根节点时，需沿着父节点指针不断向上遍历，直到找到 parent[root] == root 的节点。

基础实现（非优化）：

def find(parent, x):
    while parent[x] != x:
        x = parent[x]
    return x

2.2 合并（Union）操作：连接两个集合

合并操作需将两个元素的根节点连接起来。最简单的做法是让其中一个根节点指向另一个根节点。例如，合并 x 和 y 的集合时：

def union(parent, x, y):
    root_x = find(parent, x)
    root_y = find(parent, y)
    if root_x != root_y:
        parent[root_x] = root_y

2.3 初始问题的解决

回到社团合并的例子，假设初始时四个成员 0,1,2,3 分属不同社团。执行以下操作：

union(parent, 0, 1)  # parent[0] = 1
union(parent, 2, 3)  # parent[2] = 3
find(parent, 0) == find(parent, 2)  # 返回 False

三、并查集的优化：路径压缩与按秩合并

3.1 问题引入：树结构的退化

在基础实现中，合并操作可能导致树的结构变得“瘦长”（如链式结构），导致查找操作的时间复杂度退化为 O(n)。例如，连续合并 0→1→2→3→4 后，查找 0 的根节点需遍历整个链表。

3.2 优化策略：路径压缩

路径压缩的核心思想是在查找过程中将路径上的所有节点直接指向根节点，从而缩短树的高度。修改后的 find 函数如下：

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])  # 路径压缩
    return parent[x]

效果对比：

• 未压缩时，查找 0 需遍历 0→1→2→3→4。
• 压缩后，路径上的节点 0,1,2,3 直接指向根节点 4，后续查找效率大幅提升。

3.3 按秩合并：控制树的高度

路径压缩解决了查找的效率问题，而按秩合并（Union by Rank）则在合并时选择更优的连接方式，进一步优化树的结构。具体规则如下：

• 维护一个 rank 数组，记录每个根节点对应树的高度。
• 合并时，将秩较小的树挂载到秩较大的树下。若秩相等，则任选一方，并将选中的树的秩加 1。

实现代码：

def union_by_rank(parent, rank, x, y):
    root_x = find(parent, x)
    root_y = find(parent, y)
    if root_x == root_y:
        return
    if rank[root_x] < rank[root_y]:
        parent[root_x] = root_y
    else:
        parent[root_y] = root_x
        if rank[root_x] == rank[root_y]:
            rank[root_x] += 1

3.4 优化后的复杂度分析

经过路径压缩和按秩合并的双重优化，并查集的单次操作时间复杂度可降至 近似 O(α(n))，其中 α(n) 是阿克曼函数的反函数，在实际应用中几乎视为常数。这意味着即使数据规模达到亿级，操作时间依然可控。

四、并查集的典型应用场景

4.1 图论中的连通性问题

• 判断图的连通性：通过并查集快速判断图中是否存在连通路径。
• 动态图的维护：在边不断变化的场景中（如社交网络关系变动），并查集能高效更新连通性状态。

4.2 网络分区问题

例如，判断计算机网络中的不同子网是否连通，或合并子网时更新拓扑结构。

4.3 游戏开发中的区域管理

在游戏地图中，可以使用并查集管理不同区域的归属，例如判断两个坐标点是否属于同一阵营控制的区域。

五、实际案例与代码示例

5.1 案例：岛屿数量统计

问题描述：给定一个由 '1'（陆地）和 '0'（海洋）组成的二维网格，计算岛屿的数量（相邻的陆地块形成岛屿）。

思路：使用并查集将相邻的陆地合并为同一集合，最终统计独立集合的数量。

代码实现（Python）：

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [1] * size
        self.count = size  # 初始独立集合数
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            if self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            else:
                self.parent[root_y] = root_x
                if self.rank[root_x] == self.rank[root_y]:
                    self.rank[root_x] += 1
            self.count -= 1

def num_islands(grid):
    if not grid:
        return 0
    m, n = len(grid), len(grid[0])
    uf = UnionFind(m * n)
    directions = [(0, 1), (1, 0)]
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '0':
                uf.count -= 1  # 初始化时排除海洋
                continue
            # 合并右/下方向的相邻陆地
            for dx, dy in directions:
                x, y = i + dx, j + dy
                if 0 <= x < m and 0 <= y < n and grid[x][y] == '1':
                    uf.union(i * n + j, x * n + y)
    return uf.count

5.2 案例分析

• 初始化：每个陆地格子初始为独立集合。
• 合并操作：遍历每个陆地格子，与右侧和下方的陆地合并。
• 最终统计：count 记录独立岛屿的数量。

六、总结与进阶建议

并查集作为一种轻量级数据结构，凭借其简洁性与高效性，在算法竞赛和工程实践中均占据重要地位。本文通过逐步讲解其核心概念、优化策略及实际案例，帮助读者建立系统性认知。对于希望深入学习的开发者，建议：

1. 理解路径压缩与按秩合并的数学证明，以掌握其复杂度分析。
2. 尝试将并查集应用于其他场景，例如动态图的连通性维护。
3. 对比其他数据结构（如DFS/BFS遍历连通性）的优劣，明确并查集的适用范围。

掌握并查集不仅能够解决具体问题，更能培养对数据结构设计与优化的思想理解，为后续学习更复杂的算法奠定基础。