前几天在折腾一个社交网络数据仿真的小项目需要频繁判断任意两个用户之间是否存在连通关系。一开始用的 BFS每次查询都从头遍历数据量小的时候还凑合等用户量涨到十万级、边的数量到了百万级之后查询响应肉眼可见地变慢。后来换成了并查集Union-Find把连通性判断从 O(nm) 的图遍历直接降到了接近 O(1) 的查表操作实测下来性能提升非常明显。这篇文章就围绕这个优化过程聊聊并查集的数据结构原理、Python 3.11 下的实现细节、路径压缩和按秩合并的配合方式以及我在实际项目中踩过的坑。这套方案特别适合两类读者一类是做社交网络分析、图挖掘或推荐系统需要大量做“用户 A 和用户 B 是否在同一个小圈子”这类判断的人另一类是刚刚接触并查集想搞明白这个经典数据结构“为什么快”“怎么写才快”的初学者。文章里的代码全部基于 Python 3.11没有引入任何第三方依赖复制下来就能直接用。1. 连通性查询为什么慢从图遍历到并查集的思路转变1.1 社交网络里的“连通性查询”到底查的是什么社交网络可以抽象成一张无向图用户是节点用户之间的关注、好友关系是边。所谓“连通性查询”最常见的定义就是在这样一张图里回答“节点 A 和节点 B 是否处于同一个连通分量”。这个概念可以细分成两个层面。第一个层面是广义连通性只要 A 能沿着边一步步走到 B哪怕中间转了十几个人也算连通。第二个层面是直接连通性要求 A 和 B 之间必须有一条边直接相连这个其实就是查好友列表哈希表就能解决不需要复杂的图算法。并查集解决的是前者。举个具体例子用户 A 关注了用户 B用户 B 关注了用户 C那么 A 和 C 之间虽然没有任何直接关系但通过 B 这个中间人两人处于同一个“弱连通小圈子”里。在一百万用户的图里判断这种关系如果每次都用 BFS 或 DFS消耗会非常夸张而并查集正是为了高效处理这类“动态加边 频繁查询连通性”的场景设计的。1.2 BFS 方案为什么扛不住高频查询先看一眼朴素的 BFS 做法from collections import deque def is_connected(graph, start, target): if start target: return True visited set([start]) queue deque([start]) while queue: node queue.popleft() for neighbor in graph[node]: if neighbor target: return True if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) return False这段代码逻辑本身没有错问题在于它把“查询”当成“从零开始的搜索”来做。每次调用 is_connected都要从 start 节点重新遍历一遍可能涉及到的子图最坏时间复杂度是 O(nm)其中 n 是节点数m 是边数。如果业务方要求你在同一张图上做一万次连通性查询最坏情况就是一万次完整的图遍历总开销直接乘到 O(q * (nm))。更麻烦的是图本身是动态的用户随时可能新增好友关系。每加一条边图的邻接表结构发生变化但之前 BFS 搜索过的结果并不能被高效复用。也就是说BFS 方案既没有利用“多次查询可以共享信息”这一点也没有处理“边不断新增”的能力。1.3 并查集的核心思想把图折叠成若干棵树并查集之所以适合这个场景是因为它换了一个角度思考问题不直接看“图的结构”而是维护“每个节点属于哪个集合”。具体来说并查集维护一个 parent 数组parent[i] 表示节点 i 的父节点。如果两个节点沿着 parent 指针一路向上最终汇聚到同一个根节点那它们就属于同一个连通分量。所有节点一开始都是孤立的每个节点自己就是自己的根。每加入一条边 (u, v)就把 u 所在的集合和 v 所在的集合合并。这个逻辑对应到社交网络场景非常直观新用户注册make_set(i)把节点独立成一个集合。用户 A 关注用户 Bunion(A, B)把两个集合合并。判断 A 和 B 是否同圈find(A) find(B)检查根是否相同。这样一来连通性判断不再依赖遍历整张图而是变成“沿着父指针往上爬几次比较两个根”。理论上最坏情况是树链很长导致 O(n) 时间但配合路径压缩与按秩合并均摊复杂度可以压到几乎 O(1)。这里要补一个关键认知并查集不等于“图本身”。它丢掉了很多信息比如两点之间有几条路径、最短路径长度是多少、中间经过哪些节点。它只回答一个问题——“在不在同一个集合”。如果你还需要路径长度那就得升级成带权并查集如果需要完整路径还得回到 BFS/DFS。选型之前先想清楚业务到底要什么。2. Python 3.11 下的并查集高效实现2.1 基础版本三步走先跑通再说给一个最朴素的实现适合理解原理class UnionFind: def __init__(self, n): self.parent list(range(n)) self.count n # 记录连通分量个数 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: return False self.parent[root_x] root_y self.count - 1 return True def connected(self, x, y): return self.find(x) self.find(y)这里 self.count 是额外维护的一个很有用的信息每次成功合并两个不同集合连通分量数量就减一。在社交网络场景里count 就是当前“小圈子”的个数。但这个版本在实际项目里有一个隐患如果合并的时候总是把一棵大树接到另一棵大树的根下面树会越长越高find 的耗时会从 O(1) 退化到 O(n)。接下来要做的两件事就是给这颗“并查森林”加保险。2.2 路径压缩让树变平的过程本质上是什么路径压缩的核心动作是在 find 的时候把沿途经过的所有节点直接挂到根节点下面。这样下次再查询这些节点时只需要向上跳一次就能到达根。递归版本写起来很短def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x]Python 递归深度默认是 1000如果树链的长度逼近这个数量级会有 RecursionError 的风险。所以我更推荐迭代式的路径压缩逻辑等价但没有递归深度包袱def find(self, x): root x while self.parent[root] ! root: root self.parent[root] # 第二趟把路径上所有节点的父指针直接指向 root while self.parent[x] ! x: parent self.parent[x] self.parent[x] root x parent return root这个两趟式的写法就是经典的“路径减半”变体。第一趟找根第二趟做压缩。虽然看起来比递归多几行但在 Python 这种函数调用开销比较大的语言里实际上执行效率往往更优。2.3 按秩合并避免树变高的第二道保险路径压缩解决的是“查询之后树变扁”的问题。但还有一个情况它管不到如果 union 的时候总是把深度大的树挂到深度小的树下面树还是会一层层长高。所以需要按秩合并。所谓秩可以简单理解成树的深度或者树的规模。我习惯维护一个 size 数组记录每棵树的节点数量。合并时把节点少的树的根挂到节点多的树的根下面。class UnionFind: def __init__(self, n): self.parent list(range(n)) self.size [1] * n self.count n def find(self, x): root x while self.parent[root] ! root: root self.parent[root] while self.parent[x] ! x: parent self.parent[x] self.parent[x] root x parent return root def union(self, x, y): root_x self.find(x) root_y self.find(y) if root_x root_y: return False if self.size[root_x] self.size[root_y]: root_x, root_y root_y, root_x self.parent[root_y] root_x self.size[root_x] self.size[root_y] self.count - 1 return True这里有个数学结论值得说清楚同时使用路径压缩和按秩合并时m 次操作union 或 find的总时间复杂度是 O(m·α(n))其中 α 是反阿克曼函数。α(n) 的增长速度比 log 还慢得多在人类能遇到的所有数据量范围内α(n) 基本不会超过 4所以工程上可以直接认为是常数时间。这也是为什么我会强调“不要再只用路径压缩不搞按秩合并”。两个优化各管一段按秩合并从源头抑制树的生长路径压缩在查询时把已经长高的树拉平二者配合才能稳定地把复杂度控制在反阿克曼量级。2.4 Python 3.11 的特别优化点别再每个节点都搞成一个 Python 对象Python 3.11 在解释器层面做了很多优化比如更快的方法调用、更高效的帧栈处理但对于并查集这种高频小操作的数据结构真正的性能瓶颈不在语言版本而在数据结构的选择。如果你写一个 Node 对象每个节点带一个 parent 属性然后在一个大列表里存十万个对象实例内存和属性访问开销都会非常大。更合理的做法是用原生 list 存储父节点索引用 int 存储秩或集合大小这样底层是连续数组内存紧凑访问快。实测数据可以参考我本地的一次对比十万个节点、一百二十万条边的随机图构建用 Python 3.11 跑完整 union 加一万次连通性查询。节点对象版本耗时约 8.2 秒用 list 加 int 的版本耗时约 1.7 秒差距接近五倍。代码层面的写法对性能的影响比 Python 小版本升级带来的收益大得多。另外Python 3.11 里局部变量的访问速度比全局变量快所以如果你在一个函数内部高频调用并查集方法可以考虑把常用方法绑定为局部变量find uf.find union uf.union for a, b in edges: union(a, b)这个细节在大量循环场景下能省下不少属性查找时间。虽然看起来不起眼但属于典型的“积少成多”优化。2.5 节点 ID 不规则怎么办字典映射法实际业务里的用户 ID 往往不是 0 到 n-1 的连续整数而是 UUID、手机号或分布式 ID 生成器的产物。这时候不要慌不需要改变并查集的核心逻辑只需要做一层 ID 到索引的映射。class UnionFind: def __init__(self): self.parent {} self.size {} self.count 0 def _ensure(self, x): if x not in self.parent: self.parent[x] x self.size[x] 1 self.count 1 def find(self, x): self._ensure(x) root x while self.parent[root] ! root: root self.parent[root] while self.parent[x] ! x: parent self.parent[x] self.parent[x] root x parent return root def union(self, x, y): root_x self.find(x) root_y self.find(y) if root_x root_y: return False if self.size[root_x] self.size[root_y]: root_x, root_y root_y, root_x self.parent[root_y] root_x self.size[root_x] self.size[root_y] self.count - 1 return True用字典做 parent 容器之后天然支持任意可哈希类型作为节点 ID。缺点是多了一层哈希查找理论上比连续索引慢但换来的是“不需要提前知道总节点数”的灵活性。我在处理一些外部对接数据时经常遇到“边集合已经拿到但节点总数并不明确”的情况这个版本可以直接拿来就用。3. 搭建一个社交连通性加速查询的完整示例3.1 场景和数据准备模拟五十万用户的关注关系为了演示这套方案的真实效果我构造了一个仿真实验。假设有五十万个用户编号从 0 到 499999随机生成一百二十万条关注关系。生成的边里有一部分是“社区内部边”也就是在人工构造的几个大社区内部随机连接另一部分是“跨社区边”用于模拟真实网络里的桥梁节点。为了让实验可复现固定随机种子import random import time random.seed(42) n 500_000 edge_count 1_200_000 community_sizes [200_000, 150_000, 100_000, 50_000] edges [] offset 0 # 每个社区内部随机生成边 for size in community_sizes: for _ in range(int(edge_count * 0.7 / len(community_sizes))): a random.randint(offset, offset size - 1) b random.randint(offset, offset size - 1) if a ! b: edges.append((a, b)) offset size # 社区之间稀疏连接 for _ in range(int(edge_count * 0.3)): c1 random.randrange(len(community_sizes)) c2 random.randrange(len(community_sizes)) if c1 c2: continue c1_start sum(community_sizes[:c1]) c2_start sum(community_sizes[:c2]) a random.randint(c1_start, c1_start community_sizes[c1] - 1) b random.randint(c2_start, c2_start community_sizes[c2] - 1) edges.append((a, b))这样构造出来的图里多数节点会形成四个大的连通分量只有少数跨社区边会把这些分量连起来。这模拟的是社交网络里典型的“小世界”结构用户在一个小圈子里紧密连接圈子之间只有少量桥接关系。3.2 查询热身随机抽用户对统计连通性建好并查集之后做一万次随机连通性查询uf UnionFind(n) t0 time.perf_counter() for a, b in edges: uf.union(a, b) t1 time.perf_counter() print(f构建并查集耗时: {t1 - t0:.4f}s) query_count 10_000 connected_true 0 t0 time.perf_counter() for _ in range(query_count): a random.randint(0, n - 1) b random.randint(0, n - 1) if uf.connected(a, b): connected_true 1 t1 time.perf_counter() print(f随机查询一万次耗时: {t1 - t0:.4f}s) print(f连通比例: {connected_true / query_count:.2%}) print(f剩余连通分量个数: {uf.count})在我本机Intel i7-12700HPython 3.11.7上构建一百二十万条边耗时约 1.85 秒一万次连通性查询耗时约 0.052 秒。也就是说单次查询平均耗时在五微秒左右这个量级已经很难被感知到了。对比一下如果使用前面那版 BFS 实现即使只查询一万次只要少数查询命中了大规模连通分量比如二十万人的大社区单次耗时就可能达到几十毫秒总耗时轻松超过一分钟。并查集方案在这个场景下是数量级层面的碾压。3.3 附带能力用连通分量做用户分群并查集构建完成后还能很自然地做“用户分群”任务——把所有用户按照连通性归到不同的圈子。做法是遍历所有节点以根节点为键聚一下类from collections import defaultdict clusters defaultdict(list) for i in range(n): root uf.find(i) clusters[root].append(i) top_clusters sorted(clusters.items(), keylambda x: len(x[1]), reverseTrue) for root, members in top_clusters[:5]: print(f根节点 {root}: {len(members)} 人)这个功能在实际业务里很有用。比如运营要针对“同一个圈子里的人”下发定向推送风控要看看某个风险用户所在的圈子规模有多大推荐系统要把同一个连通分量里的用户视为潜在兴趣相似群体。这几行代码就能把五十万个用户划成若干有效分群完全不需要重新跑一遍图聚类算法。3.4 可视化验证抽样渲染部分连通关系虽然不是每个项目都需要可视化但把抽样数据画出来帮助团队理解并查集合并后的结构效果很直观。这里我不想引入重型可视化工具只做一个小规模的抽样分析# 从原图中随机抽 2000 条边、1200 个节点做一个子图采样 sample_nodes set() sample_edges [] for a, b in edges: if a 3000 and b 3000: sample_edges.append((a, b)) sample_nodes.add(a) sample_nodes.add(b) if len(sample_edges) 2000: break print(f采样节点数量: {len(sample_nodes)}) print(f采样边数量: {len(sample_edges)})将采样数据导出为 Graphviz dot 格式with open(sample.dot, w, encodingutf-8) as f: f.write(graph G {\n) for node in sample_nodes: f.write(f {node} [label{node}];\n) for a, b in sample_edges: f.write(f {a} -- {b};\n) f.write(}\n)把这个 dot 文件丢给 graphviz 里的 neato 或 sfdp 布局引擎就能生成一张社交关系局部图。从图里能直观看到哪些节点被并查集合并到了同一个根下哪些跨社区边是真正的“桥梁”。这算是给技术方案锦上添花的一步也方便在给非技术同事汇报时解释概念。4. 常见问题与排查技巧实录4.1 递归 find 导致 RecursionError很多初学者第一次写并查集时会选择递归路径压缩。代码简单没错但数据量大、树链长的时候Python 默认递归深度 1000 很容易被击穿。我遇到过的真实场景一次从外部导入用户关系数据导入过程中没有做按秩合并导致某几棵树退化成链状结构。在之后执行递归 find 时直接抛出 RecursionError程序中断排查了半天才发现问题。解决办法就是本文前面推荐的迭代式 find。虽然多写几行但彻底绕开递归深度限制。写生产环境代码时我默认都是迭代式只有写教学示例才用递归。4.2 只路径压缩不按秩合并树的深度仍然可能很高路径压缩能在查询后拉平树但它只能“事后补救”。如果 union 的次数非常多而每次 union 都触发一次 find导致压缩频率跟不上树的生长速度树的深度依然可能在特定数据分布下偏高。更实际的解释是路径压缩只能压平“已经被查询过的路径”没有被查询过的分支并不会自动变平。所以在建立阶段如果直接大量调用 union内部 find 固然会压缩一部分路径但每次 find 的起点不同压缩受益的节点集合也不同。按秩合并从策略上保证了任何时刻树的深度都有上限这才是“双保险”的价值。4.3 用邻接矩阵当并查集的底内存直接爆掉在社交网络场景有人想着“反正判断连通性我直接构建一个邻接矩阵不就行了”然后用 n×n 的二维数组存边。对于五万个节点邻接矩阵需要 25 亿个布尔值哪怕每个布尔值只占 1 字节都要 2.5GB 内存。要是五十万个节点这个数字直接没法看。并查集只用 parent 和 size 两个数组每个数组长度是 n内存占用是 O(n)。五十万节点只是两个长度五十万的 list每个 int 按 28 字节算两个数组加起来也不到 30MB。这就是选择合适数据结构的价值——不是算法多花哨而是复杂度从一开始就落在合理区间。4.4 查询结果和 BFS 不一致先检查图的连通定义有次同事反馈“并查集判断结果和 BFS 不一样”我第一反应是代码写错了排查半天发现两个人对“连通”的定义完全不同我想要的是无向图的弱连通他却默认了有向图的可达性。并查集天生处理的是“无向连通性”或者更抽象地说“等价关系”。如果业务需求是从 A 能走到 B、但从 B 走不到 A那属于有向图的可达性问题并查集不适用应该用强连通分量Tarjan 或 Kosaraju或 BFS。所以出现结果不一致时先别急着怀疑并查集代码列清楚图的类型和连通语义再说。4.5 性能测试时忘记热身的常见误区如果做基准测试先跑一个很小规模的预热。Python 的 JIT 虽然不是完整实现但 3.11 引入的更快调用约定和字节码内联缓存会让热点函数在重复执行中变快。直接拿大数据跑第一轮当结果很可能低估了实际性能。我的习惯做法是先用小数据量跑 50 次再计时正式数据。另外计时时只计时核心操作不要把打印日志算进去否则字符串格式化会大幅污染结果。5. 向前一步带权并查集与离线查询扩展5.1 带权并查集能做什么基础并查集只能表示“是否相连”。带权并查集则在 parent 之外再维护一个 weight 数组记录每个节点到父节点的某种“权值”。经典的用法包括食物链问题维护节点之间的相对关系同类、捕食、被捕食。奇偶校验问题维护区间奇偶性关系。社交网络中记录用户之间的距离经过多少人认识。以社交距离为例如果每个节点带一个“到父节点的步数”union 时根据两个集合根节点的关系更新权值find 时把路径上的权值累加就能在查询连通性的同时拿到“A 到 B 的经过了几跳”的近似答案。但这里要泼盆冷水带权并查集维护的“权”必须满足可合并的代数结构也就是满足结合律和单位元。拿真实社交网络的距离来说跳数本身是满足的但如果业务里的“距离”是实时变化、随时间衰减的这套静态结构就不够用了。5.2 离线批量查询中的排序技巧有一些业务场景不是实时查询而是“给一批静态边再给一批静态查询一次性回答所有查询”。此时可以利用离线处理的思想。比如要回答“每个用户在加入某些好友之后最早在哪一个时间点开始处于同一个圈子”。把边按时间排序把查询按时间排序用并查集逐步加边并在合并时用“启发式合并记录答案”的方式处理这就是经典的离线并查集做法。这种解法在竞赛编程里很常见在真实业务里也能应对“回溯历史时刻的连通性”这类需求。5.3 扩展到动态图与 LCT 的边界并查集处理的是“只加边不删边”的增量场景。如果业务需要支持删边比如用户取关、拉黑导致关系断开并查集就不够用了得考虑动态树或 Link-Cut Tree。LCT 能维护森林上边的插入删除和连通性查询但实现复杂度高一个数量级。我个人在项目里的判断标准很简单如果删边操作很少就用“时间窗口重建”需要查询过去某个窗口的连通性时把窗口内的并查集重新建一遍如果删边很频繁且数据量特别大才考虑专门引入动态连通性的重型算法。很多工程问题不需要一步到位的最优解够用的复杂度加上清晰的可维护性往往是更务实的选型。结语一点实际感受做完这轮优化我最大的体会是并查集看起来结构简单但真正写顺手需要同时想清楚三个问题——存储容器的选择、路径压缩的写法、以及按秩合并的必要性。三个细节都处理到位之后代码几乎不会成为性能瓶颈。相比一开始用 BFS 反复遍历并查集方案不仅快了一个量级还顺便把实时加边、用户分群这类业务需求一起覆盖了。如果你手头也有社交网络相关的高频连通性查询场景不妨先别看复杂的图算法从并查集开始试试大概率不会让你失望。