周一早上,monorepo 的 CI 又红了。报错来自 @acme/ui:找不到 @acme/core/dist/index.js。同一个 commit 在本地能过,在 CI 上重跑一次也可能过,唯一在变的是「谁先构建」。
仓库有七个 workspace 包:app、ui、api、core、icons、db、utils。真实的依赖是 app 依赖 ui 和 api,ui 依赖 core 和 icons,api 依赖 core 和 db,core、icons、db 都依赖 utils。构建脚本却只是把 packages/ 目录列一遍,按文件系统返回的顺序逐个执行 npm run build。core 碰巧排在 ui 前面时正常,反过来,ui 就会 import 一个还没产出的 dist。
这不是包管理器的问题,它安装依赖时算过顺序。缺的是我们自己那层批量脚本里的拓扑排序。下面从图是什么讲到怎么算出合法顺序、怎么发现环,以及 BFS 为什么能回答「最少几跳」。
现象:顺序错了,但错误不是每次都出现
CI 的失败率大约三成,失败一定停在 ui 或 api,错误一定是找不到 core 或 db 的产物。重跑有一半变绿,日志里每个包的开始时间看不出串行间隔。
脚本先 readdir 拿到目录列表,再按这个顺序 for 循环构建。文件系统返回顺序没有任何承诺,换机器、换容器层、换缓存都可能不同,于是「core 在 ui 前面」成了一个概率事件。
有人把列表按名字排序。这能治当下,因为 core 的字母序确实在 ui 前;但出现一个 zed-utils,或者把 core 改名成 base,字母序又对不上依赖关系。顺序应该由依赖算出来,而不是由名字碰出来。
依赖关系是一张网:包是点,「A 需要 B」是有向边。要得到合法执行顺序,需要表示它的结构、遍历它的方法,以及专门处理先后约束的拓扑排序。
图:顶点、边、方向和度
图(graph)由顶点集合和边集合组成,一条边连接两个顶点。它没有坐标、没有距离。把七个包画成七个圈,把依赖画成圈与圈之间的连线,就得到一张依赖图。
有向边带方向,写成 (u, v),从 u 指向 v;无向边不分方向,{u, v} 和 {v, u} 是同一条。判断用哪种,只问一句:这个关系反过来还成立吗?
有向的例子
包依赖:app 依赖 core,反过来不成立。社交关注:你关注某人,对方未必关注你,关注数和粉丝数是两个数字。这类关系只能画成带方向的边。
无向的例子
好友关系:平台要求双方确认,关系对称,画一条线就够。同一局域网的两台机器也常按无向处理,因为「连通」不区分谁主动。
度(degree)是跟顶点相连的边数。有向图拆成入度和出度:入度是进来的边数,出度是出去的边数。入度为 0 的点没有前置约束,可以先走;出度为 0 的点是终点。依赖图里,包的入度就是它直接依赖了几个包。
路径是首尾相接的一串边;环是起点和终点重合的路径。无向图里任意两点都可达叫连通;有向图要两个方向都可达,才叫强连通。依赖图常常不连通,总有一些孤立包,它们各自可以随便排。
这篇只讨论简单图:同一对顶点之间最多一条边,也没有自己指向自己的自环。允许重边和自环的叫多重图,处理依赖时几乎用不到;真遇到时,把重边合并成一条,自环单独当错误报出来即可。
这篇统一约定:真实项目写「A 依赖 B」,图上画成 B 到 A 的边,也就是从被依赖者指向依赖者。这样入度就是「还欠几个依赖」,入度为 0 可以立刻安装。方向约定本身不重要,全篇和代码用同一套才重要。
这张图里 utils 入度为 0,app 出度为 0;core 入度是 1,ui 入度是 2。这些数字就是安装顺序的骨架。
两种存法:邻接表和邻接矩阵
图在内存里怎么放,决定了每个操作的代价,常见的有两种。
邻接表给每个顶点挂一个列表,存它指向的所有顶点。空间是 O(V + E)。查一条边的代价是这个点的出度,遍历它的邻居也是出度,没有浪费。
邻接矩阵开一个 V 乘 V 的表格,有边填 1,没边填 0。查边是常数时间,一次下标就够;但遍历一个点的邻居必须扫完整行。空间是 O(V²),跟边数无关。
邻接表:稀疏图的默认选择
空间 O(V + E)。查边 O(出度),遍历邻居 O(出度)。依赖图、关注图、网页链接图都稀疏,边数通常只是顶点数的几倍,必须用它。
邻接矩阵:稠密图和矩阵运算
空间 O(V²)。查边 O(1),遍历邻居 O(V)。顶点只有几百、边却接近平方级,或者算法本身是矩阵乘法时,它更合适。
稀疏图必须用邻接表,这不是风格偏好。依赖图里十万个包、平均每个几十个依赖,边数几百万;矩阵要开一百亿个格子。
n = 100000
print(n * n)
print(n * n / 1024**3)
在本机 Python 3.15 上跑,输出是:
10000000000
9.313225746154785
按每格一个字节算,接近 9.3 GiB;用四字节整数存权重就是 37 GiB,还没算业务数据。邻接表在这个规模下只是几百万个整数。
稠密图反过来适合矩阵,常数级查边和访存局部性开始占优。判断标准很简单:先估 V² 和 E,哪个小用哪个。
在 Python 里,邻接表通常写成「字典套列表」或「字典套集合」。集合版本查边是平均常数,代价是每个集合对象都有额外开销;列表版本省内存,但查边要扫。依赖图主要做遍历和删边,列表就够了。
遍历:队列、栈,和那个不能省的标记
从某个顶点出发,沿边把能到达的顶点都走一遍,叫图的遍历。两种基本顺序:广度优先和深度优先。
BFS 用队列。取出队头,把它尚未访问的邻居放到队尾,于是一圈一圈地扩。DFS 用栈或递归:走到一个邻居就继续深入,走不动再退回上一层。递归调用栈本身就是那个栈,不需要自己维护。
两种遍历都必须带访问标记。图里可能有环,也可能有两条不同路径通向同一个点。没有标记,DFS 会在环上无限转,BFS 会把同一个点反复入队,直到内存耗尽。标记要记「已经进过队列或栈」,不能只记「已经处理完」。
下面在四节点环上跑一个截断到深度 8 的计数版 DFS,一次带标记,一次不带。
ring = {0: [1], 1: [2, 0], 2: [3, 1], 3: [0, 2]}
def dfs_count(graph, start, depth, visited):
if depth == 0:
return 1
total = 1
for nxt in graph[start]:
if visited is not None and nxt in visited:
continue
if visited is not None:
visited.add(nxt)
total += dfs_count(graph, nxt, depth - 1, visited)
if visited is not None:
visited.discard(nxt)
return total
print(dfs_count(ring, 0, 8, {0}))
print(dfs_count(ring, 0, 8, None))
4
121
带标记只进入 4 次,不带标记进入 121 次。四个点、深度 8,已经差三十倍;真实图上千点,不带标记就不是慢,是跑不完。
两者的代价都是 O(V + E),前提是邻接表;拿矩阵遍历会变成 O(V²)。要最短跳数、按层处理用 BFS,要判可达、做回溯用 DFS。
BFS 还有一个副产品:它天然按层输出,可以顺手记下每个点属于第几层,用来做「同层并行」的调度。DFS 记录的是入栈和出栈的先后,这个顺序能判断祖先关系,也是下一节环检测的基础。
拓扑排序:把先后约束排成一条线
拓扑排序给每个顶点排一个位置,使每条边都从排在前面的人指向后面的人。换成人话:所有前置条件都排在结果前面。安装、编译、先修课、任务调度,都是这件事。
前提是图里没有环。A 要等 B、B 又要等 A,谁也动不了,不存在合法顺序。所以拓扑排序和环检测是同一个算法的两面。
Kahn 算法四步:先算每个点的入度;把所有入度为 0 的点放进队列;每次出队一个点输出,删掉它的出边,让终点入度减一;减到 0 的再入队。循环到队列为空。
关键在最后一步的「再」。只把初始入度为 0 的点入队、删边后不补,会漏掉一批顶点;而且它不报错,只是产物在更远的下游缺失。
用七个包跑一遍。代码先把依赖表反转成边,再算入度。
from collections import deque
deps = {
"app": ["ui", "api"],
"ui": ["core", "icons"],
"api": ["core", "db"],
"core": ["utils"],
"icons": ["utils"],
"db": ["utils"],
"utils": [],
}
# 边:依赖指向依赖者;入度 = 该包自己的依赖条数
g = {p: [] for p in deps}
for p, ds in deps.items():
for d in ds:
g[d].append(p)
indeg = {p: 0 for p in g}
for p in g:
for q in g[p]:
indeg[q] += 1
def kahn(graph, indeg, key):
deg = dict(indeg)
q = deque(sorted((v for v in graph if deg[v] == 0), key=key))
order = []
while q:
u = q.popleft()
order.append(u)
for v in sorted(graph[u], key=key):
deg[v] -= 1
if deg[v] == 0:
q.append(v)
return order, deg
order1, _ = kahn(g, indeg, lambda s: s)
order2, _ = kahn(g, indeg, lambda s: s[::-1])
print("入度:", indeg)
print("顺序A:", order1)
print("顺序B:", order2)
真实输出:
入度: {'app': 2, 'ui': 2, 'api': 2, 'core': 1, 'icons': 1, 'db': 1, 'utils': 0}
顺序A: ['utils', 'core', 'db', 'icons', 'api', 'ui', 'app']
顺序B: ['utils', 'db', 'core', 'icons', 'api', 'ui', 'app']
两次只改了同层顶点的排序方向。结果都合法:utils 永远第一,app 永远最后;core 和 db、icons 可以互换,因为彼此没有依赖。这就是拓扑序不唯一,不是实现有 bug。
拿顺序 A 对照一下:utils 入度 0 先出队,core、icons、db 的入度依次归零;core 出队后 ui 还差 icons,所以不会提前;等 icons 出队,ui 才进队列。每一步取到的都是「此刻所有依赖都已就绪」的包。
工程上要让它可复现,就得给同层一个稳定的平局规则,通常按名字,或者拓扑层级加名字。代价是一次排序,收益是缓存键和日志不再漂移。
复杂度是 O(V + E):每个点进出队列一次,每条边在删边时被看一次。找入度为 0 不要每轮全表扫描,否则退化成 O(V²)。
环检测:数一数输出够不够
Kahn 天然能报环:输出顶点数小于总数,剩下的就是环上或环下游的点。让 icons 和 core 互相依赖,再跑一次:
deps2 = {**deps, "icons": ["utils", "core"], "core": ["utils", "icons"]}
g2 = {p: [] for p in deps2}
for p, ds in deps2.items():
for d in ds:
g2[d].append(p)
indeg2 = {p: 0 for p in g2}
for p in g2:
for q in g2[p]:
indeg2[q] += 1
order3, deg3 = kahn(g2, indeg2, lambda s: s)
print("有环时输出:", order3)
print("输出节点数:", len(order3), "/", len(g2))
print("入度未清零:", {p: d for p, d in deg3.items() if d > 0})
有环时输出: ['utils', 'db']
输出节点数: 2 / 7
入度未清零: {'app': 2, 'ui': 2, 'api': 1, 'core': 1, 'icons': 1}
2 小于 7,结论成立。但「剩余」不等于「环」:app、ui、api 只是被环挡住了,自己不在环上。判断存在性看数量,定位具体边要另一套方法。
三色标记是常用做法:白色表示没访问,灰色表示在当前递归路径上,黑色表示已完成。DFS 撞到灰色顶点就找到了回边,从路径里截出这一段就是环。对上面这张图跑,得到 ['core', 'icons', 'core'],两条互相依赖的边都点了出来。
环上任意一条边都能当证据,删掉它就断,所以报错应该打印整条环路径,而不是只写「检测到循环依赖」。Kahn 便宜、不用递归;三色能给路径,但受递归深度限制。常见组合是先跑 Kahn,发现数量不够再补一次三色,只为把错误报清楚。
还有一种容易忽略的情况:自环,也就是包依赖自己。它在入度里贡献 1,永远无法归零,Kahn 会直接判环。报错时应该单独提示自环,而不是让用户去翻整张图。
无权图的最短路径:为什么 BFS 就够了
「从 A 到 E 最少几跳」,在无权图上用 BFS 就能回答。BFS 按距离一层层推进,第一次从队列取出某个点时,那个距离就是最短距离;更短的路径会在更早的层里出现。
下面这张图里,A 关注 B 和 C,B、C 都关注 D,D 关注 E。
from collections import deque
social = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": ["E"], "E": []}
def bfs_hops(graph, start, target):
q = deque([(start, 0)])
seen = {start}
while q:
node, d = q.popleft()
if node == target:
return d
for nxt in graph[node]:
if nxt not in seen:
seen.add(nxt)
q.append((nxt, d + 1))
return -1
print(bfs_hops(social, "A", "E"))
3
输出 3,路径是 A 到 B 到 D 到 E。seen 集合保证每个点只入队一次,所以队列里的距离单调不减,这就是「第一次到达即最短」的依据。
这个结论只对无权图成立。边带权之后,BFS 按边数最少给出的路径可能总耗时更长,要换成按距离排序的优先队列,也就是 Dijkstra;有负权还要更麻烦的方法。选错的症状很典型:跳数最少,实际更慢。
用 DFS 找最短路的反例也很好造:它可能先沿一条长链走到目标,回头才看到旁边那条两跳的路。DFS 只保证「能到」,不保证「最短」,这正是 BFS 按层推进的价值。
一张现象对照表
下面这些现象都能在图的基本概念里找到解释,前三条对应开头那类构建脚本。
| 现象 | 真实原因 | 第一步查什么 |
|---|---|---|
| 安装或构建顺序偶尔失败,重跑能过 | 脚本按目录或名字顺序执行,没有算拓扑序 | 打印实际执行顺序,再和依赖图逐条比对 |
| 某个包一直不开始,卡到最后 | 依赖成环,没有任何点的入度能归零 | 统计已完成节点数和总数,列出剩余入度 |
| 拓扑排序少输出几个包,也不报错 | 只把初始入度为 0 的点入队,删边后没补入队 | 检查入度减到 0 时是否真的入队 |
| 构建机器内存爆掉或直接卡死 | 稀疏图用了邻接矩阵,空间按 V² 涨 | 先算顶点数和边数,比较 V² 与 E 的量级 |
| 每次构建顺序都不同,缓存命中率很低 | 拓扑序不唯一,队列顺序没有稳定的平局规则 | 固定同层排序键,或记录拓扑层级做缓存键 |
| 遍历时 CPU 占满,任务永远不结束 | 没有访问标记,或在出队时才标记 | 确认 visited 在入队或入栈那一刻写入 |
| 最短路跳数最少,耗时反而更长 | 带权图用了 BFS,按边数而不是总代价比较 | 确认边是否等权,再决定用 BFS 还是优先队列 |
| 并行安装时偶发缺文件 | 并行任务丢掉了先后约束,只剩全量并发 | 检查调度器是否按拓扑层级分批 |
边界与代价
第一,递归 DFS 的栈深度等于最长路径。Python 默认递归上限是 1000 层,一条几千个包的单链依赖就能把它打穿,抛出的还是 RecursionError,看起来和图毫无关系。深图要么改显式栈,要么用 Kahn 这种天然迭代的算法。
第二,邻接表的常数开销不小。每个点一个列表对象、每条边一个引用,一百万条边可能占到上百 MB,跨进程传输还要算序列化成本。
第三,稠密图用矩阵是对的,稀疏图别图省事。顶点上万、边只有几万时,矩阵分配会先失败;反过来真稠密时,邻接表查边又退化成 O(V)。
第四,并行安装只能发生在同一拓扑层内。把整张图丢进线程池,等于放弃拓扑排序的成果,错误会以竞态出现,最难复现。正确做法是按层推进、层内并发。
第五,拓扑序不唯一会影响缓存和审计。两次构建只要中间层顺序变了,时间戳、缓存键、日志顺序都会变。要可复现,就固定一个全序:层级优先,同层按名字。
第六,Kahn 要复制一份入度,不能直接改原图数据。原图还要留给环定位、可视化或二次调度;就地修改会让下一次调用拿到一份被删空的图,排查时很难看出问题。
小结与练习
这篇的主线可以压成三句。图是顶点和边的集合,依赖是有向边,度决定谁能先开始;邻接表让稀疏图跑得起来,遍历必须带访问标记;拓扑排序把先后约束变成一条合法排列,输出数量不够就说明有环。
下一篇讲递推与归纳。这里还有个尾巴:DFS 就是递归,而递归的代价不能靠数循环得到,得把子问题规模写进递推式。二分查找每层留一半、归并排序每层合并 n 个元素,这些结构正好是下一篇的主角。
当天可以自己验证的练习:
- 把七个包换成自己项目的依赖,跑一遍 Kahn;再用随机打乱的字典顺序跑十次,记录出现几种合法顺序,并指出哪些包的相对位置固定。
- 给依赖图加一条边制造环,先用「输出节点数小于总数」判断,再用三色 DFS 打印完整环路径,比较两种方法各自多写了多少代码。
- 把四节点环的 DFS 改成真实遍历,去掉访问标记并加五秒超时,观察它是超时还是栈溢出,解释为什么两者都可能发生。
- 用一千个顶点、三千条边构造稀疏图,分别用邻接表和邻接矩阵存一遍,打印对象数量或内存占用,验证矩阵为什么不可行。
- 把社交图每条边改成 1 到 10 的随机权重,用 BFS 和优先队列各求一次 A 到 E,找出两者结果不同的例子。