并查集 size 的优化（超详细）

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

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 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）是一种基础但极其重要的工具，广泛应用于图论、社交网络分析、动态连通性问题等领域。然而，许多开发者在初次接触并查集时，可能并未意识到其性能优化的潜力。本文将聚焦于“并查集 size 的优化”这一核心主题，通过循序渐进的讲解，帮助编程初学者和中级开发者理解优化原理、实现方法，并通过实际案例加深理解。

基础知识回顾：并查集的运作机制

什么是并查集？

并查集是一种用于管理元素之间的动态连通性的数据结构，其核心功能包括：

1. 查找（Find）：判断两个元素是否属于同一连通分量；
2. 合并（Union）：将两个不相交的连通分量合并为一个。

并查集的典型应用场景包括：

• 社交网络中判断两个人是否属于同一社交圈；
• 图论中检测图是否连通；
• 网络分区问题中的动态连通性管理。

基础实现与问题

并查集的最简实现通常采用树形结构，每个元素对应一个节点，每个节点指向其父节点。初始时，每个元素的父节点指向自己（即自成一个集合）。合并操作通过将一棵树的根节点挂载到另一棵树的根节点下完成。

未优化的实现示例

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
    
    def find(self, x):
        while self.parent[x] != x:
            x = self.parent[x]
        return x
    
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.parent[root_y] = root_x

问题分析

上述实现存在两个主要缺陷：

1. 路径过长导致查找效率低：当树的高度较大时，find操作的时间复杂度可能接近$O(n)$；
2. 合并策略不优化导致树结构失衡：随机合并可能导致树退化为链表，例如，每次将小树合并到大树，反之则可能形成“细长”的结构。

并查集 size 的优化原理

引入 size 数组的意义

为了提升并查集的效率，开发者通常采用以下两种优化手段：

1. 路径压缩（Path Compression）：在查找过程中将路径上的节点直接指向根节点，减少树的高度；
2. 按秩合并（Union by Rank）：根据树的深度（秩）决定合并方向，保持树的高度最小。

而“按 size 优化合并”是另一种常见的策略，其核心思想是：根据连通分量的大小（size）决定合并方向，确保合并后的树高度尽可能低。

size 与秩的对比

• 秩（Rank）：通常表示树的高度或近似高度，合并时将较浅的树挂载到更深的树下；
• size：直接记录每个连通分量的节点数，合并时将较小的集合挂载到较大的集合下。

为什么选择 size 优化？

想象一个社交网络场景：当两个朋友圈合并时，若将人数少的朋友圈并入人数多的群体，整体结构会更“扁平”。同理，按 size 合并能有效避免树的高度增长，从而降低查找时间。

优化后的实现步骤

1. 初始化 size 数组：每个节点的初始 size 值为 1；
2. 合并时按 size 比较：将 size 较小的集合的根节点指向 size 较大的集合的根节点；
3. 路径压缩与 size 同步更新：在路径压缩时，需同步维护 size 数组的准确性。

优化后的代码示例

class UnionFindSizeOptimized:
    def __init__(self, size):
        self.parent = list(range(size))
        self.size = [1] * size  # 新增 size 数组
    
    def find(self, x):
        while self.parent[x] != x:
            # 路径压缩：直接指向祖父节点
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x
    
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        # 将较小的集合合并到较大的集合
        if self.size[root_x] < self.size[root_y]:
            self.parent[root_x] = root_y
            self.size[root_y] += self.size[root_x]
        else:
            self.parent[root_y] = root_x
            self.size[root_x] += self.size[root_y]

时间复杂度的提升

通过路径压缩和 size 优化的结合，每次 find 和 union 操作的时间复杂度可降低至接近 $O(α(n))$，其中 $α(n)$ 是阿克曼函数的反函数，增长极慢（在实际中可视为常数）。这使得并查集在处理大规模数据时表现更稳定。

实际案例：社交网络的连通性分析

场景描述

假设我们有一个包含 100 万用户的社交平台，需要快速回答以下问题：

• 用户 A 和用户 B 是否属于同一社交圈？
• 合并两个社交圈后，新的圈子里共有多少人？

未优化 vs 优化后的对比

未优化的并查集

uf = UnionFind(1000000)
for i in range(1, 1000000):
    uf.union(i-1, i)  # 逐个合并，形成链表结构

优化后的并查集

uf_size = UnionFindSizeOptimized(1000000)
for i in range(1, 1000000):
    uf_size.union(i-1, i)  # 按 size 合并，树的高度始终为 O(log n)

关键差异

进阶技巧与注意事项

技巧 1：路径压缩的强化版本

在 find 方法中，可以采用“完全路径压缩”，即让路径上的所有节点直接指向根节点：

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

但需注意递归可能导致栈溢出，此时应改用迭代实现。

技巧 2：size 数组的维护

在合并操作中，必须同步更新 size 数组的值，例如：

self.size[root_x] += self.size[root_y]
self.parent[root_y] = root_x

否则，后续查询集合大小时会得到错误结果。

注意事项

1. 初始化的准确性：size 数组的初始值必须与节点数量严格对应；
2. 合并方向的判断：始终将较小的集合合并到较大的集合，而非随机选择；
3. 多条件合并的兼容性：若同时使用 size 和秩优化，需明确优先级。

结论

通过“并查集 size 的优化”，开发者可以显著提升数据结构的性能，使其在处理大规模动态连通性问题时表现更稳定。本文通过代码示例、对比分析和实际场景，详细阐述了 size 优化的实现逻辑与优势。对于编程初学者，建议从基础的并查集代码开始，逐步加入路径压缩和 size 优化，通过对比运行时间与树的结构变化，直观感受优化效果。而对于中级开发者，可进一步探索并查集与其他算法的结合（如 Krusky 算法），以解决更复杂的工程问题。

掌握并查集的优化技巧，不仅是对数据结构的深入理解，更是提升代码效率与工程化能力的关键一步。希望本文能成为读者学习与实践的指南，助力解决实际开发中的连通性问题。