先还原一次构建系统的发布事故。某次给两个内部包加了依赖:包 A 的构建要用包 B 生成的类型声明,包 B 又依赖包 A 的产物。构建器每一轮扫描所有包,把「依赖都已完成」的包放进队列。几轮过去,队列一直是空的,但还有三个包没编译。进程没有报错,直接拿上一次的旧产物打了镜像;等到测试环境启动失败,才发现新代码根本没进去。
问题不在缓存,也不在并发。依赖图里出现了一个环,图里每个包都在等别人,谁也无法先开始。构建器只判断「队列空了就结束」,没有判断「结束的时候是不是所有包都编译完了」。这两个条件在无环图里等价,在有环图里差得很远。
这篇讲拓扑排序:把有向图排成一条线,让每条边都从前指向后。先讲边方向和入度,再讲 Kahn 算法的排队与删边,接着用结果数量判断环,最后用 DFS 三色标记做另一种判环。它解决的正是「谁先谁后」和「永远排不上」这两件事。
现场:队列空了,活却没干完
把事故里的依赖图缩小到三个包。A 要等 B,B 要等 C,C 又要等 A。构建器的逻辑是:每一轮遍历所有未完成的包,只要它的全部依赖都已完成,就放进待办队列;从队列取出一个包,标记完成,再从下一轮开始重新判断。这个思路本身没错,错在结束条件。
第一轮,A 等 B,B 等 C,C 等 A,没有任何一个包的依赖全部就绪,队列是空的。循环退出,构建器认为工作结束。可完成的包数量是零,总包数是三。代码没有比较这两个数字,于是把「无事可做」当成了「全部做完」。如果它当时多做一次计数比较,就会立刻报出循环依赖,而不是安静地产出旧产物。
这类问题在构建系统、任务调度、课程先修、数据管道里长得一模一样:只要关系是有方向的,并且要求「先做前面的,再做后面的」,就需要一个能判断顺序是否存在的算法。拓扑排序给出的不只是顺序,还顺手回答了「这个顺序到底存不存在」。
有向无环图与入度
有向图是边带方向的图:一条边从 u 指向 v,只允许沿着这个方向走。如果沿着边一直走,永远回不到已经走过的点,这样的有向图叫有向无环图,简称 DAG(Directed Acyclic Graph)。依赖关系天然适合建成 DAG:包 A 依赖包 B,就画一条从 B 到 A 的边,表示 B 必须先完成。
入度(in-degree)是指有多少条边指向一个点。放到依赖里,入度就是「这个点还有多少个前置条件没被满足」。出度则是从这个点出发的边数,表示它被多少个后来者依赖。入度为零的点没有前置条件,可以立刻开始;入度不为零的点,必须等指向它的那些点先完成。
拓扑排序(topological sort)是把所有顶点排成一个序列,使得每条边都从序列前面的点指向后面的点。换成业务语言:每个任务都排在它所有前置任务的后面。这样的序列不一定唯一,但只要图里有环,就一个都不存在,因为环上的每个点都要求自己排在自己前面。
const graph = {
a: ['b'],
b: ['c'],
c: [],
};
上面这张图表示 a 必须先于 b,b 必须先于 c,c 没有后继。它的拓扑序只有 a、b、c 这一种。代码里用邻接表存出边,键是起点,值是一个数组,列出它能直接到达的点。注意方向:数组里存的是「后继」,不是「前驱」,这两个方向在写算法时很容易搞混。
Kahn 算法:从入度为零的点开始排队
Kahn 算法的思路很朴素:先把所有入度为零的点放进队列,表示它们现在就能做;每次取出一个点,把它加入结果,然后「删掉」它的所有出边;删边的实际做法是把每个邻居的入度减一,如果某个邻居的入度减到零,说明它的前置都完成了,也放进队列;重复到队列为空。
代码用一个数组当队列,再用一个下标指向队头,而不是每次从数组头部删除。后者在 JavaScript 里会搬移整个数组,把线性算法拖成平方级。入度用对象记录,第一次见到某个顶点时初始化为零,遇到一条指向它的边就加一。
function kahn(graph) {
const indeg = {};
for (const u of Object.keys(graph)) indeg[u] = 0;
for (const u of Object.keys(graph)) {
for (const v of graph[u]) indeg[v] = (indeg[v] || 0) + 1;
}
const queue = Object.keys(indeg).filter(v => indeg[v] === 0);
const order = [];
let head = 0;
while (head < queue.length) {
const u = queue[head++];
order.push(u);
for (const v of graph[u]) {
indeg[v]--;
if (indeg[v] === 0) queue.push(v);
}
}
return { order, hasCycle: order.length < Object.keys(indeg).length };
}
拿 a、b、c 这条链跑一遍:初始入度是 a 等于 0、b 等于 1、c 等于 1,队列里只有 a;取出 a,b 的入度减到 0 入队;取出 b,c 的入度减到 0 入队;取出 c。结果是 a、b、c,没有环。
console.log(JSON.stringify(kahn({ a: ['b'], b: ['c'], c: [] })));
// 输出:{"order":["a","b","c"],"hasCycle":false}
复杂度是 O(V+E):每个顶点进队一次、出队一次,每条边在它的起点出队时被处理一次。空间是 O(V+E),主要是邻接表和入度表。这个界很干净,没有对数,也没有优先队列;代价是它只回答顺序,不关心哪个任务更急、哪个更重。
队列还是栈:输出为什么不唯一
Kahn 算法只要求「入度为零就入队」,没有规定先取哪一个。用先进先出的队列,先就绪的先处理;用后进先出的栈,后就绪的先处理。两种都正确,但输出的序列可能不同。拓扑序本来就不唯一,只要每条边都从前指向后,任何顺序都算合法答案。
拿一个真实的依赖例子:应用依赖框架和工具库,都依赖语言。若按「依赖边」存图,应用指向框架和工具库,框架和工具库指向语言。用队列跑,输出是应用、框架、工具库、语言;换成栈,输出是应用、工具库、框架、语言。
队列:先就绪先处理
输出应用、框架、工具库、语言,顺序稳定、容易复现,适合希望结果可预测的构建缓存。
栈:后就绪先处理
输出应用、工具库、框架、语言,仍然合法。栈优先深入最近解锁的分支,适合深度优先的调度策略,但更难复现。
这里还有一个方向上的坑。按「依赖边」存图,输出的第一项是应用,最后一项是语言,这是从最上层往最下层;真正编译要先编语言,所以要么把输出反过来,要么建图时把边反过来存。反过来后,算法输出语言、框架、工具库、应用,正好可以直接执行。
如果构建缓存要求同样的输入产生同样的顺序,还要再加一层确定性:入度同时归零的点,按包名或编号排序再入队。否则对象键的遍历顺序、文件系统返回的顺序、并发完成的时间,都会让两次构建产生不同的拓扑序,缓存命中率跟着波动。
有环:结果数量少于顶点数
Kahn 算法结束时,如果结果里的顶点数量等于图里顶点总数,说明所有点都排进去了,图无环;如果少于总数,说明有一部分点始终没有等到入度归零,它们要么在环上,要么被环挡住了。这个判断比「结果是不是空」可靠得多,因为环可能只困住一部分点,其余点照样能排出来。
拿一个三点的环跑一遍:a 指向 b,b 指向 c,c 又指向 a。初始三个点的入度都是 1,队列一开始就是空的,循环一次也不执行,结果为空,数量零小于三,判为有环。
console.log(JSON.stringify(kahn({ a: ['b'], b: ['c'], c: ['a'] })));
// 输出:{"order":[],"hasCycle":true}
为什么环上的点永远等不到?因为环上每个点都有一条来自环内前一个点的入边,只有前一个点被取出,这条入边才会被删;可前一个点又要等它的前一个点,绕一圈回到自己。没有外力能打破这个互相等待,所以它们的入度永远不可能减到零。
工程上报错时,只告诉用户「有环」通常不够。更好的做法是把剩下的点收集起来,在剩余子图里继续做一次拓扑排序或深度优先搜索,找出具体是哪几个包互相依赖。构建系统如果能在日志里打出「A 等 B,B 等 C,C 等 A」,排查时间会从半天缩短到几分钟。
DFS 三色标记:另一条判环路线
Kahn 算法从「入度」入手,深度优先搜索(DFS,沿着一条路走到底再回头的遍历)则从「路径」入手。判环时给每个顶点涂三种颜色:白色表示还没访问,灰色表示正在当前这条递归路径上,黑色表示已经彻底处理完。沿着边往下走,如果走到一个灰色点,说明回到了当前路径上的祖先,环就出现了。
为什么黑色不算环?因为黑色点属于另一条已经走完的分支,从当前点走到它只是两条分支汇合,不构成回路。灰色才是关键:它代表「我还在栈里,没走完」,能回到灰色点,说明路径首尾接上了。只用一个「访问过」的布尔值不够,它分不清灰色和黑色。
function hasCycle(graph) {
const color = {};
for (const v of Object.keys(graph)) color[v] = 0;
function visit(u) {
color[u] = 1;
for (const v of graph[u] || []) {
if (color[v] === 1) return true;
if (color[v] === 0 && visit(v)) return true;
}
color[u] = 2;
return false;
}
for (const v of Object.keys(graph)) {
if (color[v] === 0 && visit(v)) return true;
}
return false;
}
用前面两张图分别跑,无环返回 false,有环返回 true。DFS 还能顺便产出拓扑序:一个点变成黑色时,把它压到结果数组的头部,或者先尾插最后整体反转,得到的就是「前置在前」的顺序,因为一个点的所有后继都处理完了它才变黑。
console.log(JSON.stringify(hasCycle({ a: ['b'], b: ['c'], c: [] })));
// 输出:false
console.log(JSON.stringify(hasCycle({ a: ['b'], b: ['c'], c: ['a'] })));
// 输出:true
DFS 的短板是递归深度。依赖链很长时,递归层数可能超过调用栈上限,浏览器或 Node 会直接抛栈溢出。工程上要么改成显式栈的迭代版本,要么在链长可控时再用递归。它的长处是能直接给出环上的路径:递归栈里从灰色点回到自己的那一段,就是一条具体的循环依赖链。
实际用途:构建、调度与先修关系
最典型的用途是构建依赖。包管理器拿到一张依赖图,先做拓扑排序,再按顺序编译;如果排序结果数量不足,就报循环依赖。真实系统还会叠加版本约束、可选依赖、平台条件,图只是骨架,但「先编译谁」这件事永远由拓扑序决定。
任务调度还有一个副产品:分层。第一轮入度为零的点是第 0 层,删边后新归零的点是第 1 层,依此类推。同层任务互不依赖,可以并行;层数就是最短串行时间。构建系统常按层决定并行度,而不是把所有点丢进线程池。
课程先修同理:能排出顺序就说明可行,排不出说明有循环要求;拓扑序只解决先后,不解决排在哪学期。
现象、真实原因与第一步排查
拓扑排序出问题时,症状通常不是「排序结果不好看」,而是「有活没干完却不报错」。下面这些情况在构建和调度系统里很常见。
| 现象 | 真实原因 | 第一步查什么 |
|---|---|---|
| 构建卡住或直接结束,日志无报错 | 依赖成环,队列取空但还有剩余点,没比较数量 | 输出顶点数是否等于总数 |
| 某个包总是最后才编译 | 边方向建反,把「被依赖」当成「依赖」 | 边的起点和终点分别代表什么 |
| 同一提交两次构建顺序不同 | 零入度点的顺序依赖对象键或输入顺序 | 是否固定了 tie-break 规则 |
| 明明没有循环却报环 | 存在自环、重复边,或把无向边当成有向边 | 是否有自环和重复声明 |
| 删掉一个依赖后顺序仍不对 | 入度没随边表更新,或残留重复边 | 入度是否从边表重新计算 |
| 大仓库排序很慢 | 每轮全量扫描,或用 shift 搬移队列 | 是否用队头下标保持线性 |
| 递归判环时栈溢出 | 依赖链太深,递归层数超过调用栈 | 是否改成显式栈的迭代写法 |
| 报错只说有环,定位不到包 | 没有记录剩余节点或当前递归栈 | 是否输出具体的循环依赖链 |
| 并行层数算错 | 把同层依赖误当成不同层,或批次推进不对 | 是否按入度归零的批次推进 |
第一行和第四行最容易误判。第一行看起来像「构建器卡死」,其实是队列空了但工作没完;第四行看起来像「算法有 bug」,其实是图里真的有一条自己指向自己的边,或者同一条依赖被声明了两次。判断时先打印图的顶点数和边数,再打印排序结果的长度,两个数字一比,方向就清楚了一半。
边界与代价
拓扑排序只适用于有向图。无向图里一条边来回都能走,任何一条边本身就是一个长度二的环,谈不上先后。另一个前提是关系必须真的构成「先后」;两个任务本来可以并行,就不该在它们之间加边,否则会人为拉长关键路径。
重复边是个隐蔽的坑。同一对依赖写了两遍,入度会加两次,删边时也减两次,通常仍然正确;但若建图只保留一条邻接边、入度却按声明次数累加,入度永远减不到零,最后误判成有环。正确做法是建图时去重。
自环更直接:一个包依赖自己,入度至少是一,永远排不上。报错信息应该点名这个包,而不是笼统地说图里有环。
动态更新也是代价。加一条边或删一条边,重算拓扑序是 O(V+E),大仓库每次全量重算并不便宜。增量排序、局部重算是优化方向,但实现复杂,先确认全量重算真的是瓶颈。
最后要分清它能回答什么。它能回答顺序是否存在、给出一个合法顺序,不能回答哪个顺序更快、哪个任务更关键、版本冲突怎么解。真实构建系统还要叠加资源、缓存、网络时间,这些不是一张 DAG 能装下的。
当天能做的练习
- 把本文的 Kahn 算法原样跑一遍,分别输入链状图和三点环,记录
order与hasCycle,并解释环图为什么一开始队列就是空的。 - 把队列换成栈,用应用、框架、工具库、语言的依赖图跑一次,对比两种输出。再把边反向存一遍,确认编译顺序变成语言在前。
- 给示例图加一条重复依赖,先不去重,观察入度和输出是否变化;再去重后重跑,记录两次结果,并说明哪一次才是业务想要的。
- 用 DFS 三色标记写一个判环函数,分别测试无环链、三点环和一个带汇合点的菱形图,确认菱形图不会被误判为有环。
- 把 Kahn 算法改成按层输出,返回一个二维数组,每一层是可以并行的任务。用依赖图验证层数,并说明总工期为什么不是顶点数,而是关键路径长度。
小结与下一篇
三句话收一下:拓扑排序把有向图排成一条满足所有先后关系的线,前提是图里没有环;Kahn 算法从入度为零的点开始,取一个点、删它的出边、把新归零的邻居入队,结果数量少于顶点数就说明有环;DFS 三色标记从路径入手,回到灰色点就是环,还能顺便给出具体的循环链。
下一篇讲并查集。拓扑排序处理的是有向关系和先后顺序,并查集处理的是无向关系和连通性:两个元素是不是在同一组、合并两组、查一个组里有多少人。它们看起来都在「管理关系」,但一个关心方向,一个只关心是否相连。理解了这一篇的入度与删边,下一篇的合并与路径压缩会更容易对照。