最近在处理一个服务依赖分析的工具时我又把 Floyd-Warshall 传递闭包算法翻了出来。需求本身很简单依赖关系是一张有向图模块 A 依赖 BB 依赖 C那么 A 应该被判定为间接依赖 C业务方要的是“任意两个模块之间有没有一条可达路径”而且查询频率非常高。刚开始我图省事直接对每个查询跑一次 DFS结果数据量一大延迟立刻变得不可接受。后来改成用 Floyd-Warshall 传递闭包算法做预计算一次把整张图所有点对的可达关系都算出来后续每次查询只是读一个布尔值速度从天级别降到微秒级。这篇文章就把这个算法的原理、实现、优化和我踩过的几个坑完整聊一遍适合正在做依赖分析、知识图谱关系查询、数据流分析这类工作的朋友也适合准备算法面试、想把动态规划思路彻底吃透的同学。1. 传递闭包到底在解决什么问题从一次依赖查询说起1.1 一个高频需求任意两点之间是否可达先明确一下问题。给定一个有向图 G(V,E)传递闭包要做的事情是对于图中任意两个顶点 i 和 j判断是否存在一条从 i 出发、经过若干条边最终到达 j 的路径。如果存在就在结果中记一个“可达”如果不存在就记一个“不可达”。这个“判断任意点对可达性”的操作在工程里太常见了构建系统判断库之间的间接依赖、权限系统判断角色是否继承某个权限、知识图谱里判断两个实体是否存在多级关系、编译器数据流分析里判断某个变量定义能否到达某个使用点本质上都是同一个模型。可以想象一张“朋友的朋友”网络我认识 AA 认识 B那么我和 B 之间就存在一条两跳路径。传递闭包做的事情就是把这个两跳、三跳乃至更长路径上的可达关系全部展开成一张“直接可达”的表。数学上如果原图有边 (i,j)闭包里一定有 (i,j)如果原图有路径 i→...→k→...→j闭包里也必须有 (i,j)。补全了所有这样的关系之后这张图就变成了具有传递性的闭包图。这里有个容易混淆的点传递闭包和“最短路径”不是一回事。最短路径关心的是“从 i 到 j 的最小代价是多少”而传递闭包只关心“到底能不能到”。一个是带权重的优化问题一个是不带权重的布尔判定问题。很多初学者看到 Floyd 这个名字第一反应是拿来算最短路径然后顺手也把传递闭包当最短路径做这其实是理解上的第一个坎。1.2 单次 BFS/DFS 的痛点和预计算的价值如果不做任何预处理最直接的做法就是对每个顶点做一次 BFS 或 DFS看它能访问到哪些点。单次遍历的复杂度是 O(VE)做 V 个点就是 O(V*(VE))。听起来好像也没多吓人但实际项目里的问题往往是“图不大查询极多”。假设图有 1024 个顶点边也算稠密E 接近 V^2。那么单次 BFS 大约是百万级的操作一次查询勉强能接受。但业务方不会只查一次线上服务每秒可能有几百上千次这样的判断请求每次都现跑一遍遍历CPU 很快就被打满。而且如果图是稠密图E 本身就是 O(V^2)每个点做 BFS 的单源复杂度就退化成 O(V^2)V 个点全部遍历一次就是 O(V^3)跟后面要讲的 Floyd-Warshall 一个量级但每次查询都重复 O(V^2)完全没有复用价值。反过来预计算的思路是把“建图”和“查询”两件事拆开。图结构如果相对稳定那么我花一次 O(V^3) 的时间把所有点对可达关系算出来存成一张 V×V 的可达矩阵。之后任何一次“i 能否到 j”的查询就是reach[i][j]取一个值复杂度 O(1)。这就是典型的“用预处理时间换查询时间”在读多写少的场景下非常划算。这个权衡思路是理解传递闭包应用价值的关键后面选型章节还会反复用到。2. Floyd-Warshall 传递闭包原理把“可达性”拆成三段式递推2.1 动态规划状态定义允许经过哪些中间节点Floyd-Warshall 系列的算法核心都建立在同一个动态规划状态上R[k][i][j]表示“从 i 到 j 的路径中间节点只允许使用编号不超过 k 的那些顶点时i 是否可达 j”。这个定义一开始有点绕但拆开就很清楚。假设所有顶点编号从 0 到 n-1那么 “不超过 k” 就是一个逐渐放开的约束。k0 时路径中间不允许经过任何其他顶点所以R[0][i][j]只在 ij 或者原图存在直接边 (i,j) 时为真。kn-1 时“中间节点不允许使用超过全部顶点”等于没有限制此时的R[n-1][i][j]就是真正的传递闭包。递推关系也顺着这个约束展开当允许使用 k 号顶点作为中间节点时从 i 到 j 的路径只有两种可能。第一种根本不需要经过 k那它已经是一条“只用前 k-1 个顶点”的路径状态是R[k-1][i][j]。第二种路径确实经过了 k那它就可以拆成两段先由 i 走到 k再由 k 走到 j这两段各自的中间节点当然也都不能超过 k-1对应R[k-1][i][k]和R[k-1][k][j]同时为真。两种情况只要有一种成立R[k][i][j]就为真。写成公式就是R[k][i][j] R[k-1][i][j] OR (R[k-1][i][k] AND R[k-1][k][j])用生活中的快递中转站来打比方原来要从城市 i 送包裹到城市 j现在新增了一个中转城市 k 的权限。要么原来就有一条不经过 k 的路要么可以先把包裹从 i 运到 k再从 k 运到 j。这个“尝试把所有节点轮流当中转站”的思路就是整个算法的灵魂。2.2 为什么最外层必须枚举中转点 k代码写起来只有三层循环但循环的顺序不是随便定的最外层必须是 k。这是初学者最容易写错、也最不容易理解的地方。核心原因是动态规划的每一层 k 都建立在完整的 k-1 层之上我们必须先把所有“允许使用前 k-1 个节点”的状态全部算完才能去计算“允许使用前 k 个节点”的状态。换句话说当你准备用 k 作为中转点去连接 i 和 j 时你需要的两个子问题i→k和k→j必须已经是“允许使用前 k-1 个中间点”的最终答案而不是半成品。如果把 i 放在最外层在处理某个 i 的时候整个 k 层还没算完后面随时可能遇到一个更长路径把之前判断为“不可达”的点对变成“可达”但外层循环已经过去了结果就漏了。举一个只有三条边的例子0→1、1→2、2→3。正确结果很明显 0 可以到 3。但如果循环顺序是for i for j for k在处理 i0、j3 时k 从 1 开始尝试此刻 1→2 和 2→3 之间的关系可能还没有被中间点 2 连通于是 R[0][3] 被判断为 false。等到外层循环推进到其他 i这个问题再也不会被重新检查结果永远漏掉。而如果把 k 放最外层处理 k2 时0→3 会被拆成 0→2 和 2→3前者在 k1 阶段已经算好后者是直接边于是正确置为 true。所以“中间点最外层”不是一个性能习惯而是正确性要求。2.3 到底和最短路径版 Floyd 是什么关系很多资料把传递闭包算法称为 Warshall 算法把最短路径称为 Floyd 算法也有合称 Floyd-Warshall 的。两者其实共享同一套动态规划框架差别只在于“合并两个子问题的运算符”。最短路径版本里状态是dist[i][j]递推是dist[i][j] min(dist[i][j], dist[i][k] dist[k][j])用“取最小值”和“加法”来合并。传递闭包版本里状态是reach[i][j]递推是reach[i][j] reach[i][j] || (reach[i][k] reach[k][j])用“逻辑或”和“逻辑与”来合并。一个是 min-plus 代数一个是布尔代数。理解了这一层两个算法的代码基本是同一个模板唯一不同的是矩阵里存的东西和合并运算。还有一点值得说在传递闭包版本里我们完全可以把三维状态数组压成二维在原矩阵上原地更新。因为布尔状态只会从 false 变成 true绝不会变回去而每一轮基于的“旧状态”即使被顺带改成了 true这个 true 也是正确的可达结论不会污染后续计算。原地更新是安全的这也是后面工程实现可以大幅省内存的前提。3. 手把手实现朴素布尔矩阵与 bitset 优化3.1 朴素实现Python 和 C 的入门写法先把最直白的版本写出来。用reach[i][j]代表 i 可达 j初始时对角线设为 true 表示自己可达自己这是自反传递闭包工程里通常需要具体看需求再根据原图边把直接相连的格子设为 true。然后三层循环跑完即可。Python 的写法def transitive_closure(n, edges): # reach[i][j] 表示 i 是否可达 j reach [[False] * n for _ in range(n)] for i in range(n): reach[i][i] True for u, v in edges: reach[u][v] True for k in range(n): for i in range(n): if reach[i][k]: for j in range(n): if reach[k][j]: reach[i][j] True return reachC 版本注意一个工程细节不要用vectorvectorbool。标准库对vectorbool做了位压缩特化返回的是代理对象而不是真正的 bool 引用遍历和并发场景下性能诡异而且很容易写出让人困惑的代码。推荐用vectorvectoruint8_t或者干脆用下一节的 bitset。C 朴素版这样写#include vector #include cstdint using ByteMatrix std::vectorstd::vectoruint8_t; void transitive_closure(int n, const std::vectorstd::pairint, int edges, ByteMatrix reach) { reach.assign(n, std::vectoruint8_t(n, 0)); for (int i 0; i n; i) reach[i][i] 1; for (auto [u, v] : edges) reach[u][v] 1; for (int k 0; k n; k) { for (int i 0; i n; i) { if (reach[i][k]) { for (int j 0; j n; j) { reach[i][j] | reach[k][j]; } } } } }这个朴素版的问题就是复杂度固定 O(V^3)而且内层循环是纯标量操作每个布尔值都要单独读一次、算一次、写一次CPU 的向量化能力完全用不上。当 n 到 2048 或 4096 时运行时间会急剧恶化。3.2 bitset 优化把 j 循环变成一行位运算优化思路很直接把矩阵的每一行看成一个二进制整数第 j 位为 1 就表示这一行对应顶点可达 j。原本内层要遍历 n 个 j现在对整行做一次按位或操作一次 CPU 指令就能处理 64 个布尔值。于是内层 j 循环从 O(n) 降到 O(n/64)总复杂度从 O(V^3) 降到 O(V^3 / word_size)。C 用std::bitset写非常简洁适合顶点数在编译期已知且不超过 bitset 大小的场景#include bitset #include vector const int MAXN 2048; using ReachRow std::bitsetMAXN; std::vectorReachRow reach(n); for (int i 0; i n; i) reach[i].set(i); for (auto [u, v] : edges) reach[u].set(v); for (int k 0; k n; k) { for (int i 0; i n; i) { if (reach[i].test(k)) { reach[i] | reach[k]; } } }注意这里reach[i] | reach[k]的语义正好对应递推公式里的for j: reach[i][j] | reach[k][j]。如果 i 能到达 k并且 k 能到达 j那么 i 一定能到达 j把 k 这一行所有“可达目标”并入 i 行即可。由于 k 是最外层循环被并入的reach[k]已经是“允许使用前 k 个中间点”后的完整状态正确性有保证。如果顶点数在运行期才确定std::bitset不够灵活可以自己写一个基于uint64_t数组的动态 bitset或者直接用 Boost 的dynamic_bitset。更取巧的做法是用 Python 的整数当作位图Python 大整数的位运算是 C 实现的性能相当好代码也很短。def transitive_closure_bitset(n, edges): reach [0] * n for i in range(n): reach[i] 1 i for u, v in edges: reach[u] | 1 v for k in range(n): mask_k 1 k row_k reach[k] for i in range(n): if reach[i] mask_k: reach[i] | row_k return reach这段代码在 n 不超过几千时跑起来非常快而且比二维列表版本省内存得多。缺点是如果 n 超过一两万Python 大整数位运算会因为跨多个机器字而变慢届时要评估是否换 C 实现。3.3 内存预算你的顶点数适合哪种方案传递闭包的矩阵需要 V^2 个存储单元这是绕不开的空间下限。但“单元”有多大决定了实际内存差异很大。用vectorvectoruint8_t就是 V^2 个字节用位压缩就是 V^2 个比特相当于 V^2/8 个字节用std::bitsetMAXN本身也是位压缩但会有一些额外的对象开销。做一个简单预算V1024 时位图方案大约 128KB字节矩阵约 1MB完全无所谓。V4096 时位图约 2MB字节矩阵约 16MB也还可以。V10000 时位图约 12.5MB字节矩阵约 100MB这就有点肉痛了但勉强能接受。V50000 时位图约 312MB字节矩阵约 2.5GB字节矩阵基本不可行。V100000 时位图也要 1.25GB单机内存就开始告急。所以我的判断是V 在 5000 以下朴素矩阵或者 bitset 都行优先写简单的版本V 在一万到几万区间必须用位压缩同时要考虑是不是有更合适的替代算法V 超过十万Floyd-Warshall 直接预计算这条路基本走不通应该回到第 4 节的稀疏图方案。这个内存评估要在开工前做别等代码写完了才发现矩阵装不下。4. 实战选型三种更符合项目情况的替代方案4.1 读多写少的静态图预计算闭包一劳永逸Floyd-Warshall 传递闭包最适合的场景就是“图基本不变但查询非常多”。典型例子是权限系统的角色继承关系角色数量几千角色之间的继承关系可能几天才改一次但每次用户请求都要判断“当前角色是否间接拥有某个权限”。这时把角色继承网建好预计算一次传递闭包后续权限校验就直接查reach[role][permission]一个布尔值搞定性能非常稳定。类似场景还有编译器的依赖关系分析、静态代码扫描里的调用关系传递、知识图谱的实体关系闭包查询。这些场景有一个共同特点图结构相对静态一次预计算可以服务海量查询。工程上我会额外建议把闭包结果序列化到磁盘或缓存起来因为图没变就不需要重算连启动时的构建时间都可以省掉。4.2 只增不减的动态图增量更新闭包如果图不是完全静态而是会不断新增边比如服务依赖图每天加入新模块每次全量重算 O(V^3) 会越来越不划算。这时候可以用增量更新新增一条边 u→v 时真正新增的可达路径是“所有能到达 u 的节点现在都能通过这条新边到达 v 能到达的所有节点”。用位图实现伪逻辑如下def insert_edge(u, v, reach): # 先保存 v 当前的可达集合 old_v reach[v] reach[u] | old_v # 所有能到 u 的点也都能经由新边到达 v 的可达集合 mask_u 1 u for x in range(len(reach)): if reach[x] mask_u: reach[x] | old_v关键点在于必须用old_v也就是插入边之前 v 的可达集合。因为新边 u→v 产生的新路径是从“x→u”接上“u→v→v的可达点”v 的可达点范围应该以插入前为准。如果 v 本身也能到达 u形成环上面的循环会在多次迭代里重复 OR 相同内容但因为位运算幂等多 OR 一次没有副作用最多浪费一点时间。增量更新的单次复杂度大约是 O(V^2 / 64)比全量重算快得多。但注意这套思路只能优雅地处理“只加边、不删边”的场景。如果要删除边闭包会收缩需要反推哪些可达关系是依赖这条边建立的逻辑非常麻烦通常不如直接重算。所以遇到频繁删边的动态图我的建议是重新评估是否真的需要维护闭包。4.3 稀疏大图SCC 缩点 拓扑序 DP 才是正解工程里真正的“大图”往往不是稠密图而是稀疏图比如微服务调用链、软件包依赖边数通常是顶点数的几倍。这种情况下直接上 Floyd-Warshall 的 O(V^3/64) 依然很浪费因为矩阵里大量状态根本没必要存。更好的方案是三步走。第一步用 Tarjan 或 Kosaraju 算法求强连通分量把每个 SCC 缩成一个点。同一个强连通分量内部任意两点互相可达闭包关系天然成立不需要逐点算。缩点之后原图变成一个有向无环图顶点数从 V 降到 C通常 C 远小于 V。第二步对有向无环图做拓扑排序。第三步按拓扑序的逆序做动态规划每个 SCC 的可达集合等于自己加上所有后继 SCC 的可达集合的并集。因为拓扑序保证后继节点先被处理完所以并集结果一定是完整的。// 假设 tarjan 已得到缩点后的 DAGdag_out[u] 是 u 的后继列表 // topo 是缩点后 DAG 的拓扑序closure 是位图向量表示某 SCC 可到达哪些 SCC std::vectorstd::bitsetMAXN closure(C); for (int u 0; u C; u) closure[u].set(u); for (int idx C - 1; idx 0; --idx) { int u topo[idx]; for (int v : dag_out[u]) { closure[u] | closure[v]; } }这个做法的复杂度大概是 O(E_dag * C / 64)比直接在原图上跑 Warshall 的 O(V^3/64) 小很多尤其是原图有大量强连通分量时收益明显。如果缩点后 DAG 依然非常稠密那说明原图结构特殊闭包矩阵本身就会比较大这时再权衡用不用全量预计算。实战中还有一个省事的细节DAG 上同一对 SCC 之间可能有多条原始边DP 合并时重复 OR 同一集合结果不受影响所以不需要特地去重直接遍历即可。另外提一个特例如果输入是无向图传递闭包本质上等价于求连通分量用并查集一次遍历就搞定根本不需要劳烦动态规划。很多人在无向图上套 Warshall 纯属杀鸡用牛刀。5. 踩坑记录和一组实测对比5.1 三个容易翻车的误区第一个误区是把传递闭包当成最短路径问题。有些代码习惯性地把矩阵初始化为一个大数然后用min和去跑最后再来判“是否小于无穷大”。这不是不行但完全没有必要而且整数加法可能溢出矩阵还得处理权重。判断连通性就用布尔矩阵只存 0 和 1逻辑清晰、内存减半用位图更是减到八分之一。第二个误区是对角线初始化的语义搞错。数学教材里的传递闭包有时不要求自己到自己但工程里“角色是否继承自己”这种问题往往需要自反闭包也就是要先把reach[i][i]设为 true。做依赖分析时如果把自反漏了可能把“模块依赖自身”误判成 false反过来有些查询不想要自反你又得在算法结束后单独处理对角线。这个需求差异一定要在写代码前和业务方确认而不是自己想当然。第三个误区是循环顺序写错。我见过不少把 k 放在最内层的版本那属于拿了一个 Floyd 求最短路径的模板只改了矩阵初始化没改循环结构。顺序错误导致结果随机漏边尤其对长路径几乎必错。判断标准很简单k 必须是最外层因为动态规划的状态定义里“允许使用前 k 个中间点”是一层层展开的。5.2 同一台机器上的量级对比我在本地用随机生成的稀疏有向图简单测过一组数据重点不是给出精确 benchmark而是让大家感受一下三种方案的数量级差异。测试环境是本机 CO2 编译稀疏图边数约为顶点数的 3 倍。顶点数朴素 uint8_t 矩阵bitset 优化SCC 缩点 拓扑序 DP512约 0.02s约 0.002s约 0.001s1024约 0.18s约 0.015s约 0.004s4096约 11s约 0.45s约 0.04s8192超过 90s约 2.8s约 0.18s可以看出 bitset 优化不是小打小闹而是直接把运行时间拉低了一到两个数量级。SCC 缩点方案在稀疏图上又进一步拉开差距因为顶点数经过缩点后显著下降需要处理的矩阵维度小了很多。需要注意的是SCC 方案在极端稠密图上收益会变小而且代码复杂度明显更高所以并不是什么场景都无脑选它。5.3 我的最终建议什么时候别用 Floyd-Warshall经过这些实践我现在的选型标准大致是这样如果顶点数在几千以内、图结构相对稳定直接用 bitset 预计算传递闭包简单可靠一次算完万事大吉如果图会动态增长但只加边不删边优先考虑增量更新成本可控如果图很大但很稀疏或者原图里强连通分量很多先缩点再做拓扑序 DP内存和速度都会好很多如果图频繁删边或者查询只是少数几个固定源点那就别硬维护闭包了退回到按需 BFS反而省心。还有一个我经常提的“小场景”参考如果用户只需要判断“某一个特定节点能到达哪些节点”也就是单源多次查询那么对每个源点跑一次记忆化 DFS把结果缓存下来总成本是 O(V*(VE))在稀疏图上往往比全量闭包更实用。Floyd-Warshall 家族算法很经典但它解决的“所有点对、任意查询、图静态”这个组合并不是所有业务查询都需要的。动手写代码之前先想清楚你到底要哪些点对的可达性比纠结算法本身更重要。最后再分享一个我在代码评审里经常强调的细节传递闭包这种预计算方案一定要把“图版本号”和“闭包结果版本”绑在一起。一旦底层依赖关系发生变化缓存必须立刻失效否则一个旧版本的闭包矩阵会让你线上排查到怀疑人生。我在实际项目里踩过一次这个坑之后养成了在闭包计算结果里附带一份“依赖图指纹”的习惯图变一次指纹就变一次查询时先比对版本再决定是否重算。这个习惯看上去多花了一点存储但换来的稳定性非常值得。