先说一个我真实遇过的场景。某社交类应用的后台有一个接口专门用来判断“两个用户是不是在同一个好友圈子”里比如产品想给用户打一个“熟人圈”的标签或者推荐位要判断两个人有没有间接好友关系。第一版实现写得非常老实每次查询就拿其中一个用户当起点把整个好友关系图 BFS 一遍看能不能搜到另一个用户。图不大的时候完全没问题等用户量涨到百万级、边数上千万之后接口开始频繁超时CPU 直接飙满最后不得已用并查集重构了整条查询链路。这篇文章想聊的就是这个优化过程。标题里的“暴力算法”不是贬义它指的是最直观、最容易想到的做法——每次查询都遍历一次关系图准确但昂贵。而并查集是一种几乎为这种“连通性查询”量身定做的数据结构能把“合并好友关系”和“查询是否同一圈子”的代价都压到近似常数级。从暴力 BFS 到并查集的改造代码量反而更少性能却能提升几个数量级。适合读这篇内容的人有两类一类是刚接触并查集、想知道它到底能解决什么实际问题的学生或开发者另一类是已经在写社交、知识图谱、标签聚合类功能被“动态连通性查询”性能卡住的后端工程师。前几节我会从暴力做法讲起把复杂度账算清楚后面再给出可复现代码和带权并查集的扩展场景最后附上我自己踩过的一些坑。1. 先看暴力解法是怎么“爆”的1.1 把好友关系查询翻译成计算机问题社交平台的好友关系天然是一张“无向图”用户是节点两个用户之间的好友关系是一条边。因为朋友关系是双向的所以这张图没有方向性。现在你有一个查询形如“A 和 B 是不是同一个连通分量”意思是从 A 出发沿着好友关系能不能一路走到 B。这个查询其实只关心“通不通”不关心“怎么走、走多远”。暴力算法的做法就是每次查询都跑一次图的遍历。从 A 开始 BFS 或者 DFS维护一个 visited 数组一层一层往外面扩直到找到 B 为止如果整个图都扩散完了也没找到就说明 A 和 B 不连通。这个做法的优点是简单逻辑零思考缺点也是致命的每次查询的代价和图的规模挂钩。如果产品还要求“给出 A 和 B 之间的共同好友数量”或者“最短路径长度”那 BFS 是必要的因为这些问题需要真正的路径信息。但只是判断“是否连通”BFS 就属于杀鸡用牛刀了它在遍历过程中收集到了大量你用不到的信息——完整的可达节点集合。1.2 暴力查询的时间账我把复杂度算给你看。假设图里有 V 个用户E 条好友关系。一次从 A 出发的 BFS最坏情况下要跑遍整个图代价是 O(V E)。如果系统每天有 M 次这类查询总代价就是 O(M * (V E))。代入现实数据感受一下。假设 V 100 万一百万个用户平均每个用户有 200 个好友那 E ≈ 1 亿实际社交网络边数会更多因为一条边同时算在两端用户头上这里粗略估算。再假设每天有 10 万次“是否同一圈子”的查询。暴力算法在最坏情况下需要处理的边数规模大约是100,000 * (1,000,000 100,000,000) ≈ 10^13 次操作量级10 万亿这个数量级单机就算每秒处理一亿条边也要十多个小时才能跑完查询。这还没算 BFS 过程中反复分配队列、标记 visited 的内存开销。真实场景当然不会每次都这么极端但只要有人恶意刷接口、或者碰到一个大连通块延迟立刻失控。这里我还要强调一个容易被忽视的问题BFS 的 visited 数组在每次查询中都要重新分配或重置。在 V 很大的时候光是初始化 visited 数组的开销就是 O(V)也就是说哪怕图的边不多你每次查询也要付出“清扫全部用户”的代价。这个细节在日常写代码时很容易被忽略但它恰恰是压垮性能的稻草之一。2. 并查集的核心两招优化让查询接近 O(1)2.1 最朴素的并查集到底在维护什么并查集解决的是“动态连通性”问题支持两种操作一是连接两个节点在好友场景里就是“添加好友关系”二是查询两个节点之间是否连通。它把“同一个连通分量”抽象成一个集合每个集合选出一个“代表元素”两个节点连通当且仅当它们属于同一个代表元素之下。最朴素的做法是用一个数组parent[]记录每个节点的父节点。每个集合是一棵树树的根就是集合的代表元素。find(x)沿着 parent 指针往上找根union(x, y)先分别找 x 和 y 的根如果根不同就把某棵树的根接在另一棵树的根下面。代码很短class NaiveUnionFind: def __init__(self, n): self.parent list(range(n)) def find(self, x): while self.parent[x] ! x: x self.parent[x] return x def union(self, x, y): rx self.find(x) ry self.find(y) if rx ! ry: self.parent[rx] ry这个版本能不能用能。但它有一个致命缺陷如果 union 的顺序不巧树会退化成一条链。比如依次执行union(0,1)、union(1,2)、union(2,3)……每次都把前面的根接到后面最后 parent 数组变成一条长长的链表find的最坏复杂度从 O(1) 退化到 O(N)。所以必须引入下面两个优化。2.2 路径压缩把树压平成“明星结构”路径压缩的思路是既然find(x)最终要找到树的根那就顺手把路径上经过的所有节点直接挂到根下面。这样下次再查这些节点时一步就能跳到根。实现上只需要在 find 里多做一步递归或迭代的“回溯挂载”。def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x]为什么路径压缩有效因为并查集只关心“每个集合的代表元素是谁”不关心树长什么形状。路径压缩把链式结构变成了“明星结构”——所有节点直接指向根查询路径从 N 步缩到 1 步。每次 find 都会主动削平路径用得越久树越平。2.3 按秩合并防止树悄悄长歪路径压缩能压平查询路径但如果在 union 阶段就避免树长高效果会更稳定。按秩合并也叫按树高合并的思想很朴素每次合并两棵树时把“矮”的树接在“高”的树下面。这里“秩”可以指树的高度通常维护一个 rank 数组也可以指树的规模size。用规模合并的效果通常更好因为大集合的查询频率往往更高把规模小的集合并到规模大的集合下能让平均查询成本更低。def union(self, x, y): rx self.find(x) ry self.find(y) if rx ry: return if self.rank[rx] self.rank[ry]: self.parent[rx] ry elif self.rank[rx] self.rank[ry]: self.parent[ry] rx else: self.parent[ry] rx self.rank[rx] 1按秩合并单独用可以保证任意时刻树高不超过 O(log N)路径压缩单独用可以保证多次查询后的摊还复杂度也在一个很小的范围。但两者配合时效果达到最优——单次 find 的摊还复杂度是反阿克曼函数 α(N)在 N 超过宇宙原子总数之前这个值不会超过 5。换句话说几乎可以当 O(1) 用。2.4 为什么两者配合后几乎每次操作都是常数很多人看到“反阿克曼函数”会发怵其实你只需要知道一个直观结论和普通的平衡树 O(log N) 不一样α(N) 是一个增长慢到离谱的函数。1 亿个节点的并查集单次操作的摊还代价和常数操作几乎没区别。我再用一个比喻解释路径压缩和按秩合并为什么缺一不可。按秩合并保证树不会“长得太歪”类似于你每次合并时量一下两边的规模把小大厦接到大广场下面路径压缩则是每次 find 时顺手把沿途所有小节点直接挂到广场中心让它们下次不用绕路。没有按秩合并极端情况下路径压缩要面对的是一条长链虽然压缩能改好但最坏情况下单次操作仍然可能付出 O(N)没有路径压缩按秩合并的树高是 O(log N)查询需要走 log N 步虽然不差但离“常数级”还有距离。两个一起用才是并查集真正封神的地方。3. 实操改造暴力遍历换并查集3.1 数据准备与查询接口设计假设你手里有一张好友关系表每一行表示“uid_a 和 uid_b 是好友”。现在要把 BFS 暴力查询改成并查集工作可以分为两步。第一步预处理读入全部关系数据对每个关系执行 union(a, b)。这一步把历史上所有的好友关系都合并进并查集。处理完之后凡是连通的用户会在同一个集合里。第二步查询要回答“a 和 b 是否在同一个圈子”只需要执行 find(a) find(b)。如果业务上还需要知道“圈子大小”可以在 init 阶段维护一个 size 数组每次 union 时把两个根节点的 size 加起来这样也能顺手拿到每个集合的规模。需要特别注意的是好友关系是“只增不减”的。并查集天然支持不断添加新关系但不支持删除已有的关系。如果你的业务里包含“解除好友关系”这种操作并查集就不能直接用了得配合线段树分治或者倒序处理来离线解决这个问题我会在第 5 节展开。3.2 完整代码示例与复杂度对比下面是一个适用于生产环境的 C 版本写法上做了两个工程优化路径压缩用非递归实现避免极端情况下递归栈过深rank 用集合规模代替顺手支持圈子大小的统计。#include vector class DisjointSet { public: explicit DisjointSet(int n) : parent(n), size(n, 1) { for (int i 0; i n; i) parent[i] i; } int find(int x) { // 非递归路径压缩先找根再沿路把节点挂到根上 int root x; while (parent[root] ! root) root parent[root]; while (parent[x] ! x) { int next parent[x]; parent[x] root; x next; } return root; } void unite(int a, int b) { int ra find(a); int rb find(b); if (ra rb) return; // 按集合规模合并小的并到大的 if (size[ra] size[rb]) { parent[ra] rb; size[rb] size[ra]; } else { parent[rb] ra; size[ra] size[rb]; } } bool same(int a, int b) { return find(a) find(b); } private: std::vectorint parent; std::vectorint size; };对应 Python 极简版适合框架原型验证class UnionFind: def __init__(self, n): self.parent list(range(n)) self.size [1] * n def find(self, x): while self.parent[x] ! x: # 顺便把当前节点挂到爷爷节点上虽然不是标准两趟压缩但足够好用 self.parent[x] self.parent[self.parent[x]] x self.parent[x] return x def unite(self, a, b): ra, rb self.find(a), self.find(b) if ra rb: return if self.size[ra] self.size[rb]: ra, rb rb, ra self.parent[rb] ra self.size[ra] self.size[rb] def same(self, a, b): return self.find(a) self.find(b)两种语言的复杂度一样构建并查集时每条关系调用一次 unite代价接近 O(1)所以整体预处理复杂度是 O(E · α(V))之后每次查询是 O(α(V))。和暴力 BFS 的 O(V E) 相比差距是数量级的。如果你对“数量级”感知不深我建议在实际项目里加一行计时日志对比改造前后同一批查询的耗时会非常有冲击力。3.3 大规模用户下的工程细节用户 ID 往往不是连续的整数。如果你直接用用户 ID 作为 parent 数组的下标就需要开一个巨大的数组这在真实场景下不可接受。解决方案是先做一遍离散化或者用哈希表懒初始化离散化把用户 ID 映射到 0 ~ n-1 的连续整数适合在预处理阶段把所有用户一次性读进来。哈希表懒初始化不预分配数组在第一次遇到某个 ID 时才给它分配数组位置。适合用户量巨大、且孤立用户很多的场景能省掉大量“从未出现过的节点”所占用的内存。另外一个工程细节是内存对齐。C 的 vector 对 1 亿个节点来说大约 400MB这还不算 size 数组。如果你的服务内存紧张可以用 uint32_t 代替 int或者把 size 只存在根节点上复用 parent 数组的空间。对于 32 位系统或者嵌入式场景这些细节会直接影响能不能跑起来。我实际做过的项目里还遇到过一种情况同一对用户之间可能存在多条关系记录比如“关注私信发红包”各生成一条。这种重复记录不会影响并查集正确性union 同一对节点顶多多做一次 find但它会白白增加预处理时间。遇到这种数据建议在预处理前先用哈希集合对关系表去重能省不少时间。4. 扩展带权并查集能多回答一类问题4.1 需要维护“权重”的好友场景普通的并查集只回答“连通 or 不连通”。但有些场景需要回答“两个用户之间的关系值是多少”。搜索热词里出现的“带权并查集”就是干这个的。举一个社交产品里的例子每个用户和好友之间有一个“亲密度”或者“信任分值”产品想知道“A 和 B 之间的总关系值”是多少。如果这个关系值满足“可传递的差值关系”比如 A 到 B 是 3B 到 C 是 5那么 A 到 C 应该是 8那就可以用带权并查集维护。另一个经典场景是“食物链”A 吃 B、B 吃 C问 A 和 C 的关系这也是差值传递关系。注意带权并查集只适用于“关系可以累加传递”的场景。好友之间的“亲密度”通常是私有的A 和 B、B 和 C 之间的亲密值并不能推导出 A 和 C 的亲密值这种场景只能用其他算法不能硬套带权并查集。4.2 带权并查集的实现与公式带权并查集在普通并查集的基础上多维护一个weight[x]表示节点 x 到它父节点的“权值”。当 x 指向根节点时这个权值就是 x 到根的权。路径压缩的时候权值要跟着更新。递归写法如下def find(self, x): if self.parent[x] ! x: r self.find(self.parent[x]) self.weight[x] self.weight[self.parent[x]] self.parent[x] r return self.parent[x]核心是这一句weight[x] weight[parent[x]]。因为 parent[x] 在被压缩后已经指向根它的 weight 表示“parent[x] 到根的权”而 x 原本的 weight 表示“x 到 parent[x] 的权”两者相加自然就是“x 到根的权”。合并两个集合时如果我们要维护的关系是val[x] - val[y] w其中 val 表示节点到根的值合并的公式需要小心推导。假设 x 的根是 rxy 的根是 ry现在要让 y 所在集合并到 x 所在集合把 ry 的父节点设为 rx那么需要设置weight[ry] weight[x] w - weight[y]。推导过程很简单但也很容易搞反方向所以我在代码里注释解释一遍def unite(self, x, y, w): rx, ry self.find(x), self.find(y) if rx ry: # 已在一个集合用已有信息校验 w 是否正确 return (self.weight[x] - self.weight[y]) w # 合并让 rx 成为 ry 的父节点 self.parent[ry] rx # 需要满足weight[x] - (weight[ry] weight[y]) w # 所以weight[ry] weight[x] - w - weight[y] self.weight[ry] self.weight[x] - w - self.weight[y] return True这里我把 weight 定义为“当前节点到根的权”而 weight[ry] 表示 ry 到 rx 的权。合并后 y 到根的权等于 weight[y] weight[ry]而 x 到根的权是 weight[x]关系式是weight[x] - (weight[y] weight[ry]) w解出来就是上面那个公式。如果你习惯把 weight 定义为“根到当前节点的权”公式会变成weight[ry] w weight[y] - weight[x]方向完全相反。两种定义都行但代码里必须统一不然调试到你怀疑人生。4.3 它不能回答的问题带权并查集能回答差值型关系但碰到以下情况就无能为力了不可传递的关系值。比如“A 和 B 的亲密值”“B 和 C 的亲密值”无法推导出 A 和 C 的亲密值因为亲密值不是差值运算。需要“最值”信息的关系。并查集维护的是线性累加关系要回答“A 到 B 路径上的最大边权”这类问题需要用 Kruskal 重构树或者倍增 LCA。动态删除关系。和普通并查集一样带权版本也不支持删除操作。换句话说并查集族只是一件工具不是万能钥匙。设计技术方案时先判断问题的数学结构是不是“无向连通性”是不是“差值可传递”如果两个都不满足就别硬套。5. 常见问题与排查实录5.1 高频踩坑速查表我把实际开发中遇到的并查集相关问题整理成一张表方便你直接对照排查。症状可能原因解决方案find 递归栈溢出树深度过大改为非递归 find或把递归深度调大优先建议非递归查询结果偶尔错误路径压缩时权值更新顺序不对先递归 find 父节点再更新 weight最后改 parent合并后性能没有提升只做了路径压缩没做按秩合并加上 size/rank 比较小集合并入大集合用户 ID 不连续导致数组过大直接用用户 ID 做下标离散化或哈希表懒初始化同一对好友多条关系记录数据源未去重预处理时用哈希集合去重需要删除好友关系时结果不对并查集不支持删除离线倒序处理或线段树分治5.2 一次线上查询超时的修复记录这里分享一个排查案例。某次线上接口耗时告警我拿到调用链后发现瓶颈正是“判断两个用户是否在同一社群”的接口。早期实现是用 BFS用户量不大时没问题后来社群做了一轮拉新其中一个超级大社群覆盖了全站 30% 的用户每次查询只要落在那个大社群上BFS 就要遍历几十万个节点。定位过程很简单热力图显示 query 耗时高度集中在少数几个 uid 上拉出耗时日志后看到单次查询在 800ms 到 2s 之间波动。当时我先想的是“加缓存”把 uid 到连通分量 ID 的映射缓存起来。这确实能解决一部分问题但新关系不断产生缓存失效频率很高而且群体很大时缓存重建代价依然很高。后来决定直接上并查集启动时加载全量关系建集后续新增关系实时 union。改造后单次查询稳定在 1 微秒上下接口耗时直接从秒级降到 0.5ms 以下。而这个优化只多花了几十行代码。这个案例给到我两条经验。第一遇到“动态连通性查询”先想并查集不要急着上缓存因为并查集本身就是一套“天然实时一致的连通性索引”。第二如果关系表特别大预处理建并查集的启动时间可能很长解决方案是分批异步构建构建期间用旧逻辑降级或者提前把并查集的状态序列化成快照存起来服务启动时直接加载快照。最后再补一个我个人的小习惯并查集的 parent 数组初始化时我通常会尽量用iota(parent.begin(), parent.end(), 0)一次性填充而不是在循环里逐个赋值。虽然节省的时间在绝对值上不多但代码更干净。另外find 写完后记得在 submit 前用几组简单样例跑一遍先手动构建一个 5 节点的图手动模拟几次 union 和查询确认结果后再上真实数据。别嫌土这种小图验证能挡住 80% 的初始化错误。