这次我们来看一个数据结构中的经典问题并查集。很多人在学习算法时觉得并查集的概念很“玄学”抽象难懂代码实现更是无从下手。这篇文章的目标很直接帮你彻底搞懂并查集从抽象概念到两种核心实现Quick-Find 和 Quick-Union的源码实战让你能自己动手写出来并理解其性能差异。并查集Union-Find是解决动态连通性问题的高效数据结构。它不关心节点之间具体的连接路径只关心它们是否属于同一个集合。这个特性让它在处理“朋友圈划分”、“网络连接检查”、“岛屿数量”等问题时效率远超其他数据结构。对于开发者来说学习并查集的核心价值在于面试高频大厂算法面试必考知识点。竞赛利器在算法竞赛中是解决连通性问题的标准工具。工程基础理解其优化思想路径压缩、按秩合并对设计高性能系统有帮助。本文将带你完成一次深度实战。我们会先理解并查集到底在解决什么问题然后手把手实现最直观的 Quick-Find 算法分析其性能瓶颈接着实现更高效的 Quick-Union 算法并引入路径压缩优化最后通过LeetCode经典题目来验证我们的实现。你将看到清晰的代码、每一步的操作演示以及时间复杂度对比。1. 核心能力速览并查集是什么能做什么在深入代码之前我们先快速了解并查集的核心特性。它不是一个库或者一个需要安装的工具而是一种数据结构的思想和实现模式。能力项说明核心问题动态连通性问题。支持快速合并两个集合以及查询两个元素是否属于同一集合。主要操作find(p): 查找元素p的根节点集合代表。union(p, q): 合并元素p和q所在的集合。时间复杂度未经优化的朴素实现最坏可达O(N)。经路径压缩和按秩优化后近似O(1)。空间复杂度O(N)N为元素数量。通常使用一个长度为N的数组来存储父节点信息。适用场景网络节点连通性、社交网络好友关系、图像像素连通区域、变量名等价性编译器等。不适合场景需要知道具体连通路径的场景。并查集只回答“是否连通”不记录“如何连通”。并查集的“玄学”感往往来自于其利用数组存储树形结构的巧妙设计以及“代表元”的思想。接下来我们通过两种最经典的实现方式来破除这种抽象。2. 理解并查集从实际问题出发假设我们有一个社交网络有10个人编号0-9。最初每个人都是一个独立的圈子单身。查询我们想知道5号和9号是不是朋友属于同一个圈子。合并如果5号和9号成了朋友那么他们所在的整个圈子就需要合并。随着关系的建立圈子会越来越大。并查集就是为了高效处理这种“合并集合”和“查询归属”操作而生的。关键抽象每个集合用一棵树来表示。树的根节点是这个集合的“代表”或“老大”。find(x)操作就是找到x的根节点老大。union(x, y)操作就是将x所在树的根连接到y所在树的根上或者反之从而让两棵树变成一棵树两个集合合并为一个。理解了这个模型我们来看第一种实现。3. 环境准备与代码框架我们的“环境”很简单就是任何支持你熟悉编程语言的开发环境。本文将使用Python进行演示因其语法清晰易于理解。你可以轻松地将其转化为Java、C或Go。前置条件一台能写代码的电脑。一个文本编辑器或IDE如VSCode、PyCharm。Python 3.x 环境如果你用Python。我们首先定义一个并查集的基类明确接口class UnionFind: 并查集基类定义通用接口 def __init__(self, n: int): 初始化并查集包含 n 个元素 (0 到 n-1) :param n: 元素总数 self.count n # 连通分量的数量 # 具体数据结构由子类实现 pass def find(self, p: int) - int: 查找元素 p 的根节点集合标识 :param p: 元素索引 :return: 根节点的索引 raise NotImplementedError def union(self, p: int, q: int) - None: 连接元素 p 和元素 q :param p: 元素 p 的索引 :param q: 元素 q 的索引 raise NotImplementedError def connected(self, p: int, q: int) - bool: 判断元素 p 和元素 q 是否相连属于同一集合 :param p: 元素 p 的索引 :param q: 元素 q 的索引 :return: 相连返回 True否则 False return self.find(p) self.find(q) def get_count(self) - int: 返回当前连通分量的数量 :return: 连通分量数量 return self.count接下来我们实现两种具体的子类。4. 实现一Quick-Find 算法核心思想让同一个连通分量中的所有元素其id[i]的值完全相同这个值就是该分量的“根”。find(p)操作极快直接返回id[p]但union(p, q)操作较慢需要遍历整个数组来修改分量ID。4.1 数据结构与初始化class UnionFindQuickFind(UnionFind): Quick-Find 版本并查集 def __init__(self, n: int): super().__init__(n) # 初始化每个元素的组号就是自己 self.id [i for i in range(n)] def find(self, p: int) - int: # 查找操作非常快O(1)时间复杂度 return self.id[p]初始化后数组id的状态为[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]表示10个独立的集合。4.2 Union 操作实现与性能分析合并操作是Quick-Find的瓶颈所在。def union(self, p: int, q: int) - None: p_id self.find(p) q_id self.find(q) # 如果 p 和 q 已经在同一个集合中则无需操作 if p_id q_id: return # 将 p 所在集合的所有元素的 id 都改为 q 的集合 id for i in range(len(self.id)): if self.id[i] p_id: self.id[i] q_id # 连通分量减少一个 self.count - 1操作演示执行union(4, 3)。find(4) 4,find(3) 3。遍历数组将所有值为4的元素只有id[4]的值改为3。数组变为[0, 1, 2, 3, 3, 5, 6, 7, 8, 9]。分量数由10变为9。再执行union(3, 8)。find(3) 3,find(8) 8。遍历数组将所有值为3的元素id[3], id[4]的值改为8。数组变为[0, 1, 2, 8, 8, 5, 6, 7, 8, 9]。分量数变为8。性能分析find():O(1)极快。union():O(N)每次合并都需要遍历整个数组。对于N个元素进行N次合并操作时间复杂度是O(N²)。这在数据量大时是无法接受的。5. 实现二Quick-Union 算法核心思想使用树形结构。id[i]存储的是元素i的父节点。根节点的父节点指向自己。find(p)需要向上追溯找到根节点union(p, q)只需要将一棵树的根连接到另一棵树的根上。5.1 数据结构与 Find 操作class UnionFindQuickUnion(UnionFind): Quick-Union 版本并查集 def __init__(self, n: int): super().__init__(n) # 初始化每个元素的父节点都是自己即自己是自己的根 self.parent [i for i in range(n)] def find(self, p: int) - int: # 不断向上查找父节点直到找到根节点parent[x] x while p ! self.parent[p]: p self.parent[p] return p初始化后数组parent状态为[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]。5.2 Union 操作实现def union(self, p: int, q: int) - None: p_root self.find(p) q_root self.find(q) if p_root q_root: return # 将 p 的根节点连接到 q 的根节点上 self.parent[p_root] q_root # 连通分量减少一个 self.count - 1操作演示执行union(4, 3)。find(4) 4,find(3) 3。将parent[4]设为 3。数组变为[0, 1, 2, 3, 3, 5, 6, 7, 8, 9]。此时树的结构是3是4的父节点。再执行union(3, 8)。find(3) 3,find(8) 8。将parent[3]设为 8。数组变为[0, 1, 2, 8, 3, 5, 6, 7, 8, 9]。注意id[4]仍然是3但3的父节点现在是8。树的结构是8 - 3 - 4。性能分析find():O(h)h为树的高度。最坏情况下树退化成链表h N复杂度为O(N)。union():O(h)因为主要开销在find根节点上。虽然union操作不再需要遍历整个数组但树可能变得很高导致find操作变慢。在最坏情况下按顺序union形成长链进行N次操作的时间复杂度仍是O(N²)。6. 优化路径压缩与按秩合并Quick-Union 的主要问题是树可能变得不平衡。有两种经典优化可以极大改善性能使每次操作的均摊时间复杂度接近O(1)。6.1 路径压缩 (Path Compression)在find操作时顺便将查找路径上的所有节点都直接指向根节点使树变得更扁平。class UnionFindPC(UnionFindQuickUnion): 带路径压缩的 Quick-Union def find(self, p: int) - int: # 方法一循环式路径压缩推荐易理解 root p # 先找到根节点 root while root ! self.parent[root]: root self.parent[root] # 再次遍历将路径上的所有节点直接指向根 while p ! self.parent[p]: next_node self.parent[p] self.parent[p] root p next_node return root # 方法二递归式路径压缩代码简洁但可能有递归深度限制 # if p ! self.parent[p]: # self.parent[p] self.find(self.parent[p]) # 递归查找并压缩 # return self.parent[p]6.2 按秩合并 (Union by Rank)在union操作时总是将“矮”的树接到“高”的树下避免树的高度增长过快。这里的“秩”(rank)可以近似理解为树的高度。class UnionFindOptimized(UnionFind): 同时使用路径压缩和按秩合并的优化版本最常用 def __init__(self, n: int): super().__init__(n) self.parent [i for i in range(n)] self.rank [1] * n # 初始化每个树的秩为1 def find(self, p: int) - int: # 递归式路径压缩 if p ! self.parent[p]: self.parent[p] self.find(self.parent[p]) return self.parent[p] def union(self, p: int, q: int) - None: p_root self.find(p) q_root self.find(q) if p_root q_root: return # 按秩合并将秩小的树根连接到秩大的树根下 if self.rank[p_root] self.rank[q_root]: self.parent[q_root] p_root elif self.rank[p_root] self.rank[q_root]: self.parent[p_root] q_root else: # 两棵树秩相等任意连接但被连接的树根秩需要加1 self.parent[q_root] p_root self.rank[p_root] 1 self.count - 1经过这两种优化并查集的效率已经非常高足以应对绝大多数算法问题。7. 功能测试与效果验证LeetCode 实战理论讲完了我们通过一道经典的LeetCode题目来验证并查集的威力。题目 LeetCode 547. 省份数量问题描述有 n 个城市其中一些彼此相连另一些没有相连。如果城市 a 与城市 b 直接相连且城市 b 与城市 c 直接相连那么城市 a 与城市 c 间接相连。省份是一组直接或间接相连的城市组内不含其他没有相连的城市。给你一个 n x n 的矩阵 isConnected 其中isConnected[i][j] 1表示第 i 个城市和第 j 个城市直接相连而isConnected[i][j] 0表示二者不直接相连。返回矩阵中省份的数量。解题思路这正是并查集的典型应用——动态连通性问题。每个城市是一个元素。遍历矩阵如果isConnected[i][j] 1就执行union(i, j)。最后统计并查集中连通分量的数量即可。代码实现使用优化版并查集class Solution: def findCircleNum(self, isConnected: List[List[int]]) - int: n len(isConnected) uf UnionFindOptimized(n) for i in range(n): # 矩阵是对称的可以只遍历一半但遍历全部也没问题 for j in range(n): if isConnected[i][j] 1: uf.union(i, j) return uf.get_count() # 假设 UnionFindOptimized 类已定义如上测试用例# 输入isConnected [[1,1,0],[1,1,0],[0,0,1]] # 解释城市0和1相连城市2独立。 # 预期输出2 solution Solution() print(solution.findCircleNum([[1,1,0],[1,1,0],[0,0,1]])) # 输出2通过这个例子你可以清晰地看到并查集如何将问题抽象化并用极简的代码高效解决。你可以尝试用 Quick-Find 和未优化的 Quick-Union 实现同样的功能并对比运行时间直观感受性能差异。8. 性能对比与适用场景总结我们来对比一下几种实现的性能实现方式find时间复杂度union时间复杂度N次操作时间复杂度特点Quick-FindO(1)O(N)O(N²)查找极快合并极慢易理解。Quick-UnionO(h)O(h)O(N²) (最坏)合并变快但树可能退化查找变慢。Quick-Union 路径压缩接近 O(1)O(h)O(N log N)查找路径被压缩效率提升。Quick-Union 按秩合并O(h)O(log N)O(N log N)树高度得到控制合并更平衡。优化版 (路径压缩按秩合并)近似 O(1)近似 O(1)近似 O(N)工程实践标准效率最高。如何选择学习理解从 Quick-Find 和 Quick-Union 开始明白基本思想。面试手撕必须掌握优化版路径压缩按秩合并这是标准答案。算法竞赛直接使用优化版模板。生产环境根据语言选择高效库如C的std::union_find或使用优化版实现。9. 常见问题与排查方法在实现和使用并查集时你可能会遇到以下问题问题现象可能原因排查方式解决方案数组越界错误find(p)或union(p, q)中的 p, q 超出了初始化大小 n。检查输入的元素索引是否在 [0, n-1] 范围内。在函数入口添加边界检查或确保外部调用合法。死循环递归版递归实现find时父指针设置错误形成了环。使用小数据测试或打印parent数组观察。检查union操作确保是将根节点相连。使用循环版find更安全。结果不正确1.union前未正确找到根节点。2. 连通分量计数count逻辑错误。在每次union后打印parent数组和count与手动推导对比。仔细核对find和union的逻辑确保count只在成功合并时减1。性能低下大数据超时使用了未优化的 Quick-Find 或 Quick-Union。分析算法时间复杂度替换为优化版本。务必使用路径压缩和按秩合并。“按秩合并”中“秩”的理解错误误将“秩”等同于树的精确高度。理解“秩”是树高的上界在路径压缩后可能不精确但用于比较是有效的。记住按秩合并的目的是平衡不要求高度绝对精确。10. 最佳实践与使用建议模板化将优化版的并查集代码UnionFindOptimized作为模板保存遇到连通性问题直接套用。初始化大小在构造函数中一次性分配足够大的数组避免动态扩容。路径压缩选择递归写法代码简洁但可能存在递归深度限制Python默认约1000层。对于超大N10^5建议使用循环写法。计数维护count变量非常有用可以直接获取当前集合数量如在“岛屿数量”问题中。灵活变通并查集存储的不一定是整数可以是任何有唯一标识的对象。通常做法是先用哈希表给对象分配一个整数ID。理解本质并查集的优势在于忽略连接细节只维护连通关系。如果问题需要知道具体的连接路径则需要使用DFS/BFS或图算法。并查集从看似“玄学”的抽象到清晰的两类实现Quick-Find, Quick-Union再到近乎O(1)的优化体现了算法设计中“空间换时间”和“扁平化组织”的核心思想。掌握它不仅能解决一大类算法题更能提升你对数据组织方式的认知深度。下次遇到“是否连通”、“有多少个组”这类问题你的第一反应就应该是它。