图系列第 7 篇：拓扑排序与 DAG

嘿，朋友，欢迎回到图系列。这是第 7 篇，主题是拓扑排序与 DAG。如果只看名字，拓扑排序听起来像是某种高深的数学仪式，但实际上它解决的是我们每天都会遇到的日常问题：先有鸡还是先有蛋？哪门课应该先修？哪个模块应该先编译？哪个任务应该先执行？一句话说清楚，拓扑排序就是给一堆”必须分先后”的事情排出一个合法顺序。

在第 5 篇里，我们认真学过了深度优先搜索 DFS，认识了前序、后序和递归栈，也知道了”完成时间”这个隐藏的时间戳。在第 6 篇里，我们学会了用三色标记法检测有向图的环：白色是还没访问，灰色是正在递归栈上，黑色是已经完工；一旦发现灰色邻居，就说明图里有环。今天这两样东西都会以新身份再次登场：DFS 的后序顺序反过来，就是拓扑排序的一种写法；而三色标记的”灰色邻居”思想，会在环检测环节和我们重逢。如果你对这两篇的记忆已经模糊，建议先回去翻一翻，因为今天的内容是它们最漂亮的合体。

老规矩，先给你一个动手的机会。下面的可视化实验室支持你亲手搭图、加边、跑算法，后面每讲完一个算法，都建议回来实际拖一拖、点一点，看看每一步的入度变化和输出顺序是不是和文章里手算的一致。

好，出发。先从最朴素的问题讲起。

1 问题：什么任务必须先做？

1.1 三个每天都在发生的场景

场景一：大学选课。 想象你是一名计算机系学生，课表里有这样几条规则：必须先学完”程序设计基础”，才能选”数据结构”；必须学完”数据结构”，才能选”算法分析与设计”；必须学完”微积分”，才能选”线性代数”；而”概率论”又要求先学过”线性代数”。这些规则就是”先修关系”，英文叫 prerequisite。你现在要给自己排一份学习计划：一学期学几门课无所谓，但每一门课都必须满足”它的所有先修课都已经学完”这个条件。如果排课系统不遵守这些关系，你会在上”数据结构”时完全听不懂”指针和链表”，因为老师默认你已经会写函数了。

场景二：编译与构建。 你在公司维护一个大型前端项目，代码被拆成几十个模块。模块 B 引用了模块 A 导出的工具函数，模块 C 又同时引用了 A 和 B。当构建系统开始编译时，它必须先让 A 产出可用的产物，再编译 B，最后编译 C。如果把顺序搞反，B 编译到一半发现”找不到 A 提供的函数”，报错就来了。大型项目里这种依赖链可能长达几十层，靠人工排顺序完全不现实，必须交给工具自动算。

场景三：任务调度。 周末你要准备一顿大餐招待朋友：先要去超市买菜，回来洗菜切菜，炖汤要提前两小时开始，烤箱要提前预热，蛋糕面糊搅拌好之后才能进烤箱，而餐桌布置最好在上菜前完成。人和人不一样，但”先买菜再切菜”这种硬性先后关系是客观存在的。如果你先把菜切好再去超市，蔬菜会在你出门的半小时里氧化变黄。任务调度系统（比如 CI/CD 流水线、数据库迁移脚本、云上的一键部署）每天处理的就是这种问题：把一堆任务按照依赖关系排成一条可执行的时间线。

这三个场景看起来风马牛不相及，但抽象之后完全是同一个数学对象：有一堆”东西”（课程、模块、任务），它们之间有一些”必须先于”的关系，我们想找出一条线性的执行顺序，让所有先后关系都被满足。 图论给了这套抽象一个标准建模方式：把每个东西看成一个顶点，把”X 必须在 Y 之前”看成一条从 X 指向 Y 的有向边，记作 X → Y。于是选课问题变成了一张有向图，构建问题变成了一张有向图，做饭问题也变成了一张有向图。而”排出一个合法的执行顺序”，就是在这张有向图上求一次拓扑排序。

下面这张图把上面说的选课规则画了出来，箭头从先修课指向后续课程：

graph LR
    A["程序设计基础"] --> B["数据结构"]
    B --> C["算法分析与设计"]
    D["微积分"] --> E["线性代数"]
    E --> F["概率论"]

在这张图里，“程序设计基础 → 数据结构”的意思就是：程序设计基础必须在数据结构之前学。注意箭头方向很有讲究：边永远从”必须先完成的”指向”依赖它的”。有的资料习惯反过来画（从后置课指向先修课），那会带来完全不同的算法细节，所以看别人的代码之前，先确认他用的哪种方向约定，这是所有图算法菜鸟的第一个大坑。

1.2 什么是”合法的先后顺序”

假设上面这张选课图一共只有 5 门课：程序设计基础、数据结构、算法分析、微积分、线性代数、概率论（其实是 6 门，别急，我们数一下：程序设计基础、数据结构、算法分析、微积分、线性代数、概率论，正好六门）。现在让你给出一份学习顺序，比如：

1. 程序设计基础
2. 微积分
3. 数据结构
4. 线性代数
5. 算法分析
6. 概率论

这个顺序合法吗？我们一条边一条边地检查。程序设计基础 → 数据结构：程序设计基础在第 1 位，数据结构在第 3 位，前者确实在后者之前，通过。程序设计基础 → 算法分析？等一下，这张图里没有这条边，实际上算法分析只依赖数据结构。微积分 → 线性代数：第 2 位在前、第 4 位在后，通过。线性代数 → 概率论：第 4 位在前、第 6 位在后，通过。数据结构 → 算法分析：第 3 位在前、第 5 位在后，通过。全部通过，所以这是一个合法的先后顺序。

现在换一个顺序：程序设计基础、数据结构、微积分、概率论、线性代数、算法分析。检查线性代数 → 概率论这一条边就会发现：线性代数在第 5 位，概率论在第 4 位，概率论居然跑到了它的先修课前面！这就是一个非法顺序。从这里我们能提炼出合法的形式化定义：把图的所有顶点排成一行（或者说排成一个线性序列），使得对图中每一条有向边 u → v，u 在序列中的位置都严格位于 v 之前。 满足这个条件的序列就叫这张图的一个拓扑序，英文叫 topological order；而求这个序列的过程，就是拓扑排序，英文叫 topological sort。

注意这里有个容易混淆的点：拓扑排序既可以指”算法过程”，也可以指”算法输出的结果”，就像”排序”既可以指排序的动作，也可以指排好的序列。在中文语境里，“做一次拓扑排序”通常指运行算法；“得到一个拓扑排序”通常指得到结果序列。这两个用法都合法，看上下文即可。

1.3 先问一句：图里能允许环吗？

在动手设计算法之前，有一个问题必须回答：如果图里存在环，还能不能排出合法的顺序？答案是不能。假设有三门课 A、B、C，规则是 A 先于 B、B 先于 C、C 先于 A，也就是 A → B → C → A 首尾相接。现在请你试着把它们排成一行：如果 A 在 B 前面（满足第一条），B 在 C 前面（满足第二条），那么传递下来 A 应该在 C 前面，可第三条边偏偏要求 C 在 A 前面。无论怎么排，总会有一条边指向错误的方向。更形象地说，这是一个”三个人互相等对方先动手”的死锁：A 等 B 学完，B 等 C 学完，C 又等 A 学完，谁也不肯先开始，课程永远排不出来。

这个发现极其重要，它直接划定了拓扑排序的适用范围：只有有向无环图（DAG）才有拓扑排序。 所以在正式讲算法之前，我们必须先认真认识一下 DAG 这个老朋友。

2 DAG：有向无环图

2.1 定义与直觉

DAG 是 Directed Acyclic Graph 的缩写，中文叫”有向无环图”。 拆开来看有三个要素：

• 有向：每一条边都有方向，u → v 和 v → u 是两条不同的边，含义完全相反。前文说过，方向的约定是”先做 → 后做”，所以有向性是依赖关系的天然载体。
• 图：顶点加边的集合。顶点可以是课程、模块、任务、状态，边表示它们之间的关系。
• 无环：图中不存在任何一条路径能让你从某个顶点出发，沿着箭头走一圈再回到自己。注意”路径”可以经过多个顶点，所以无环不仅要求没有”自己指向自己”的自环，也要求没有 A→B→C→A 这样的长环。

一句话直觉：DAG 就是”只有过去和未来、没有轮回”的有向图。 时间不会倒流，依赖不会绕圈，原因永远在结果之前。你可以把 DAG 想象成一条不断分岔、永不回头的大河：水从源头流向大海，支流可以汇合，但水永远不可能流回上游。

这里要特别提醒：无环和有向是缺一不可的。 一张无向图即使连通性再好，只要它不是有向图，就谈不上拓扑排序；反过来，一张有向图如果带环，也无法排序。另外，DAG 并不要求连通：顶点可以分成好几块互不相连的区域，甚至可以有孤立顶点（没有任何边的顶点），它们同样属于合法的 DAG。下面这张图把”无环”和”有环”放在一起对比，左边是标准的 DAG，右边是多了一个环的反例：

graph LR
    subgraph DAG["左边：有向无环图"]
        direction LR
        A["A"] --> B["B"]
        A --> C["C"]
        B --> D["D"]
        C --> D
    end
    subgraph 反例["右边：有环，不是 DAG"]
        direction LR
        X["X"] --> Y["Y"]
        Y --> Z["Z"]
        Z --> X
    end

左边的图里，无论你从哪个顶点出发沿箭头走，都走不回自己：A 出发只能一路向下到 B 或 C，再到 D 就结束了。右边的图里，X → Y → Z → X 形成闭合回路：沿着箭头走一圈又回到 X，这就是环。判断”是不是 DAG”不能靠肉眼随便看看，尤其是顶点多、边多的时候，必须用算法严格检查，这就是第 6 篇学的三色标记检测有向图环，也是今天 Kahn 算法顺手就能完成的副产物。

2.2 为什么环就是”依赖死锁”

我们再用一个更现实的例子体会”环 = 死锁”到底意味着什么。假设你要发布一个前端项目，里面有三个模块：UI 组件库、请求封装库、业务页面。规则是：页面依赖请求库，请求库依赖 UI 库，UI 库又依赖页面（比如 UI 库里的某个组件要从页面配置里读取主题）。画成图就是：页面 → 请求库 → UI 库 → 页面。

构建系统面对这张图时会彻底傻眼：要构建请求库，得先构建 UI 库；要构建 UI 库，得先构建页面；要构建页面，得先构建请求库。三个模块互相等待，形成一个闭环，任何一个都无法先开工。真实的构建系统遇到这种情况会立刻报错：“检测到循环依赖：页面 → 请求库 → UI 库 → 页面”，然后拒绝构建，因为它知道继续等下去只会等到天荒地老。

graph LR
    P["业务页面"] --> R["请求封装库"]
    R --> U["UI 组件库"]
    U --> P

有趣的是，环的规模不影响结论：A→B→A 这样的两节点环是死锁，A→B→C→D→A 这样的四节点环同样是死锁。唯一特殊的情况是自环，即某条边从顶点指向它自己：A → A 意味着”必须先完成 A 才能开始 A”，这在依赖系统里等价于”永远无法开始”，当然也算环。Kahn 算法和 DFS 三色检测对自环的处理和其他环完全一致，都会自动发现它。

从这里还能得到一个重要推论：环检测是拓扑排序的前置体检。 给任何有向图做拓扑排序，第一件事就是确认它是不是 DAG；如果带环，直接宣告”无解”并报告环的位置，比硬排出一个乱七八糟的序列有意义得多。好消息是，今天要学的两种拓扑排序算法（Kahn 算法和 DFS 后序写法）都内置了环检测能力：跑完算法，如果发现顶点没有全部排进序列，就说明图里有环。这也是为什么第 6 篇反复强调三色标记”迟早要用上”——今天就是兑现的日子。

2.3 DAG 的两个基础引理

正式写算法之前，先证明两个简单但极其有用的引理，它们会直接变成 Kahn 算法的设计灵感。

引理一：任何非空的 DAG 至少有一个入度为 0 的顶点。 入度（in-degree）指的是有多少条边指向这个顶点。反证法：假设一张 DAG 的每个顶点入度都至少为 1，那么随便挑一个顶点 v₁，因为它的入度 ≥ 1，必然存在一条边 u₁ → v₁；再看 u₁，它也有入度 ≥ 1，所以又存在 u₂ → u₁；一路倒推下去，由于顶点数量有限，走 V 步之后必然有一个顶点重复出现，这些重复的顶点之间的路径就构成了一个环，与”DAG 无环”矛盾。所以结论成立：任何 DAG 都至少有一个”没有依赖”的起点。

引理二：任何非空的 DAG 至少有一个出度为 0 的顶点。 证明完全对称：假设每个顶点出度都 ≥ 1，那么从任意顶点出发沿箭头一直走，有限步内必然回到某个曾经走过的顶点，同样产生环。所以任何 DAG 都至少有一个”不依赖别人”的终点。

这两个引理合在一起给出了一个极其自然的排序思路：既然 DAG 里一定存在”没有任何前置依赖”的顶点，那我们就把它拿出来放到序列最前面；把它拿掉之后，剩下的图仍然是 DAG（去掉一个顶点不会凭空造出环），所以又可以找到新的入度为 0 的顶点……不断重复，直到所有顶点都被拿出来。这就是下一章 Kahn 算法的核心直觉：像剥洋葱一样，一层一层剥掉”当前没有依赖”的顶点。

另外顺便记一个 DAG 的规模性质：在简单图（没有自环、没有重边）的假设下，V 个顶点的 DAG 最多有 V(V-1)/2 条边，这个上界在顶点排成一条完整链时达到。也就是说，如果边数多于 V(V-1)/2，这张图一定不是 DAG。这个性质虽然不如两个引理常用，但面试时偶尔会用来做快速剪枝，知道即可。

3 拓扑排序：把 DAG 拉成一条直线

3.1 正式定义

有了 DAG 做基础，拓扑排序的定义就可以写得很严谨了。给定一张有向图 G = (V, E)，其中 V 是顶点集合、E 是边集合。图 G 的一个拓扑序是一个长度为 |V| 的线性序列 v₁, v₂, …, vₙ，满足：对 E 中任意一条边 u → v，u 在序列中的下标都小于 v 在序列中的下标。 换句话说，每条边的起点都必须排在终点前面。能够构造出拓扑序的有向图，必须是 DAG；反过来，任何 DAG 都一定存在至少一个拓扑序（这个”反过来”就是引理一 + 剥洋葱思路的直接推论，也是后面 Kahn 算法正确性的根基）。

这里值得强调一下”线性序列”的含义。图的本质是二维甚至多维的结构：一个顶点可以同时是很多条边的终点，也可以同时是很多条边的起点，关系像一张网。拓扑排序做的事情就是把这张网拉成一条直线，并且要求拉直的过程中不能扯断任何一条边——每条边的方向在直线上依然保持”从前到后”。用行话讲，拓扑排序是在找一个线性扩展（linear extension）：把图的偏序关系扩展成一个全序关系。数学上，如果 u 到 v 之间存在一条有向路径，那么 u 必须排在 v 前面；对于没有路径关系的两个顶点，它们谁前谁后都无所谓，这正是”不唯一性”的来源。

为了方便后面反复引用，我们把这一章用作例子的图固定下来。它一共有 6 个顶点：A、B、C、D、E、F，边如下：

• A → B（A 是 B 的前置）
• A → C（A 也是 C 的前置）
• B → D（B 是 D 的前置）
• C → D（C 也是 D 的前置）
• D → E（D 是 E 的前置）
• E → F（E 是 F 的前置）

graph TD
    A["A"] --> B["B"]
    A --> C["C"]
    B --> D["D"]
    C --> D
    D --> E["E"]
    E --> F["F"]

你可以把它想象成一条课程的流水线：A 是最基础的入门课，B 和 C 是两门平行进阶课，D 需要 B 和 C 都学完，E 需要 D，F 需要 E。注意这张图里有两条平行分支（A→B→D 和 A→C→D），它们在 D 处汇合，这种”分叉又汇合”的结构是真实依赖图里最常见的形状，也是拓扑序不唯一的根源。

3.2 两个都合法的结果

先来手算一个合法拓扑序。我们的目标是：把 A、B、C、D、E、F 六个顶点排成一行，让每条边的起点都在终点前面。最容易想到的办法是：A 没有前置，先放 A；A 放完之后，B 和 C 的前置（也就是 A）都满足了，可以放 B，然后放 C；B、C 都放完，D 的前置齐了，放 D；接着 E，最后 F。得到的序列是：

A → B → C → D → E → F

graph LR
    A1["A"] --> B1["B"]
    B1 --> C1["C"]
    C1 --> D1["D"]
    D1 --> E1["E"]
    E1 --> F1["F"]

检查一遍：A→B（1 在 2 前）、A→C（1 在 3 前）、B→D（2 在 4 前）、C→D（3 在 4 前）、D→E（4 在 5 前）、E→F（5 在 6 前），六条边全部满足，这是一个合法拓扑序。

但如果你换一个选择：A 放完之后，不先放 B 而是先放 C，会得到另一个序列：

A → C → B → D → E → F

graph LR
    A2["A"] --> C2["C"]
    C2 --> B2["B"]
    B2 --> D2["D"]
    D2 --> E2["E"]
    E2 --> F2["F"]

再检查一遍：A→B（1 在 3 前）、A→C（1 在 2 前）、B→D（3 在 4 前）、C→D（2 在 4 前）、D→E（4 在 5 前）、E→F（5 在 6 前），同样全部满足。两个序列都合法，而且 B 和 C 的相对位置正好相反。这说明拓扑排序的答案不唯一：只要图里存在”互不依赖”的两个顶点（既没有 A 必须排在 B 前的关系，也没有 B 必须排在 A 前的关系），它们之间就存在两种可能的相对顺序。

这里必须澄清一个常见的误解：不唯一不代表”随便排都行”。把两个合法序列之外的排列拿出来试，比如 A → B → D → C → E → F：检查 C→D 这条边，C 在第 4 位，D 在第 3 位，边从第 4 位指向第 3 位，违反了”从前到后”，所以这个序列非法。D 的入度是 2，它必须同时排在 B 和 C 后面；在 B 和 C 都就位之前，D 绝对不允许提前出现。

graph LR
    A3["A"] --> B3["B"]
    B3 --> D3["D"]
    D3 --> C3["C"]
    C3 --> E3["E"]
    E3 --> F3["F"]

（上图画的就是这个非法序列的”拉直”结果，注意 D 和 C 之间的箭头方向变成了从后往前，这就是犯规的标记。）

3.3 不唯一性到底由什么决定

什么时候拓扑序不唯一？精确答案是：只要存在两个顶点 u、v，满足 u 不能通过路径到达 v，v 也不能通过路径到达 u（即它们之间没有先后关系），就可以交换它们的相对位置得到另一个合法拓扑序。 用数学语言说，这样的两个顶点在图对应的偏序关系中是不可比较的。在刚才的例子里，B 和 C 就不可比较：B 到不了 C（B 的后代是 D、E、F），C 也到不了 B（C 的后代同样是 D、E、F）。

反过来，如果两个顶点之间存在一条有向路径，比如 A 到 F（A→B→D→E→F 或 A→C→D→E→F），那么在任何合法拓扑序里 A 都必须严格排在 F 前面，这个顺序是刚性的，绝不允许改变。由此得到一个有趣的观点：拓扑排序的”自由度”全部来自图中那些彼此不可达的顶点对。 图越”稀疏”、分支越多，合法拓扑序的数量往往越大；图越接近一条完整的链，合法拓扑序就越少——一条严格链状图（A→B→C→D）只有一个拓扑序。

还有一个细节值得注意：虽然 B 和 C 可以交换，但它们的交换会影响后续顶点的”可选时机”，却不影响最终是否合法。比如序列 A→B→C→D→E→F 和 A→C→B→D→E→F 里，D 的位置都恰好排在 B、C 之后；只要 B、C 都先于 D，D 就不会违约。所以在处理依赖问题时，我们通常只关心”找到一个合法拓扑序”，而不关心具体是哪一个；只有在某些特殊需求下（比如希望字典序最小的拓扑序、希望某个关键任务尽量靠前）才需要给算法附加额外的选择策略，这一点第 8 章会专门讨论。

3.4 一个小练习：数一数有几种

趁热打铁，来做一道计数练习。请看下面这张更小的图：A → B、A → C、B → D、C → D，一共 4 个顶点 4 条边。它的拓扑序有几种？

graph TD
    A["A"] --> B["B"]
    A --> C["C"]
    B --> D["D"]
    C --> D

答案是 2 种：A → B → C → D 和 A → C → B → D。推理过程如下：A 是唯一入度为 0 的顶点，必须第一；D 的入度为 2，必须等 B 和 C 都出现，所以必须最后；中间只剩 B 和 C，它们互不依赖，可以任意交换，于是有 2 种排列。你可以试着数一数本章 6 顶点例子的拓扑序数量：其实也是 2 种，因为 B、C 之外的顺序全部被链状关系锁死了（A 第一，D 必须接在 B、C 后，E、F 依次跟随），只有 B、C 可以互换。

更一般地，计算一张 DAG 的拓扑序总数是一个 #P 困难问题（比 P 困难得多，即使图不大也可能无法在多项式时间内精确数完），所以遇到”数一数有多少种合法拓扑序”的题目时，如果顶点数超过二十个，基本可以断定题目要的不是暴力枚举。我们实际应用中几乎不会去数总数，只关心”找一种”或者”找字典序最小的那一种”。

3.5 从定义到算法：还差一个执行策略

定义说得很清楚，但定义本身没有告诉我们怎么高效地找到拓扑序。最笨的办法是枚举所有排列，逐个检查是否满足所有边，复杂度是 V! 乘以 E，V 稍大就彻底爆炸，显然不可行。我们需要一个聪明的策略：每一次决策都只依赖当前”已经就绪”的顶点，绝不回头。 下一章的主角 Kahn 算法，就是用”入度”来精确刻画”就绪”这个概念的：一个顶点什么时候可以被排进序列？当且仅当它的所有前置都已经排过了，等价地说，它的入度（尚未被排掉的前置数量）降到 0 的时候。沿着这条思路走下去，拓扑排序的算法就呼之欲出了。

4 Kahn 算法：从入度为 0 开始剥

4.1 算法的直觉：剥洋葱与发入场券

Kahn 算法由 Arthur B. Kahn 在 1962 年提出，是拓扑排序最经典、也最好懂的算法。它的直觉可以浓缩成两句话。

第一句话是剥洋葱：一个 DAG 就像一颗洋葱，最外层的顶点是”没有任何前置依赖”的顶点，可以立刻拿走；拿走之后，原本被它们挡住的下一层顶点变得”没有前置了”，于是又可以拿走；如此一层一层往里剥，直到整颗洋葱剥完。剥的顺序，就是拓扑序。这个比喻和 2.3 节的引理一严丝合缝：每次剥完一层，剩下的图依然是 DAG，所以永远至少还有一个”入度为 0”的顶点可以继续剥，绝对不会中途卡死（除非图里有环）。

第二句话是发入场券：把每个顶点想象成一场演出，只有”所有前置演出都已经结束”的演员才能登台。我们用一张表记录每个顶点还差多少个前置演出没结束（这就是入度表）；每当一场演出结束，就给所有依赖它的演员”减一张待办”，当某个演员的待办减到 0 时，他就拿到了入场券，可以进入候场队列。候场队列里永远只装着”可以立即登台”的演员，谁上台都合法。

为什么这一定可行？因为拓扑排序只要求”前置先于后置”，并不要求同层顶点之间有顺序。剥洋葱时我们总是选择当前入度为 0 的顶点，也就是说选择时它的所有前置都已经在输出序列里了，所以把它放到序列末尾一定不会违反任何边的方向；而它的后继们因为”少了一个前置”，离就绪更近了一步。把这一系列”选择就绪顶点”的动作重复 V 次，所有顶点就都被安放进序列了。

你可能会问：为什么不直接用一个普通的”就绪集合”，而是要用队列？答案是：队列在这里只是一个容器，具体是队列、栈还是优先队列，影响的是同一批就绪顶点谁先出场的次序，不影响最终结果是否合法。 用普通队列会得到”先就绪先上场”的拓扑序；用栈会得到”后就绪先上场”的拓扑序；用优先队列则可以得到字典序最小的拓扑序（第 8 章详谈）。Kahn 算法的精髓不在于队列本身，而在于”入度归零才入场”这条铁律。

4.2 两个关键数据结构

Kahn 算法只需要两个数据结构，干净利落。

第一个是入度表 indeg。 这是一个长度为 V 的数组，indeg[v] 记录”还有多少条边指向 v”。初始时，我们遍历一遍邻接表：对每条边 u → v，把 indeg[v] 加一。这样统计完之后，indeg[v] 的含义非常清楚：v 的所有前置都还没被排掉时，v 要等待的次数。 当某个前置 u 被排进序列，我们就对 u 的每个后继 v 执行一次 indeg[v]—，表示”v 少了一个等待对象”。当 indeg[v] 从某个正数变成 0，就意味着 v 的所有前置全部就位，v 可以出场了。

有人可能会疑惑：入度不是图的静态属性吗？为什么算法里它会变化？这里的关键是：算法中的入度不是原始图的入度，而是”剩余图”的入度。 每排掉一个顶点 u，就相当于从剩余图里删掉 u 以及所有以 u 为起点的边；那些边原本贡献的入度，自然要逐一扣掉。所以更准确地说，indeg[v] 表示”v 在剩余图中还有多少前置没被处理”。理解了这个视角，后面的环检测结论（输出数不足 V 就是有环）就顺理成章了。

第二个是就绪队列 queue。 它装的是当前入度为 0、可以立刻排进序列的顶点。初始化时，我们把所有入度为 0 的顶点全部入队——注意是一口气全部入队，而不是只入队一个。这一点非常重要：一个 DAG 可能同时有多个”起点”，比如本章例子里如果再加一个与 A 平行的顶点 G，G 和 A 都可以第一时间入队。漏掉任何一个，都会导致算法少处理一部分顶点。

主循环长这样：

1. 从队列头部取出一个顶点 u。
2. 把 u 追加到输出序列 order 的末尾。
3. 遍历 u 的所有后继 v：把 indeg[v] 减一；如果减完之后 indeg[v] 等于 0，就把 v 加入队列。
4. 队列为空时循环结束。
5. 检查 order 的长度：如果等于 V，返回 order；否则返回”无解”（图里有环，或更准确地说，剩余图里存在环）。

这里第 3 步的检查条件要写成”减完等于 0 才入队”，而不是”减完小于等于 0 就入队”。因为每条边只会被它的起点处理一次，indeg[v] 只会被恰好减到 0 一次；如果写成小于等于 0，在存在重复边或代码 bug 时可能会让同一个顶点重复入队，输出序列里出现重复顶点。用严格等于 0 的判断，从结构上杜绝了这种问题。

4.3 TypeScript 实现

我们用 TypeScript 写一个完整的 Kahn 算法。输入约定：顶点编号为 0 到 n-1，邻接表 adj 是二维数组，adj[u] 里存放所有 u 指向的顶点；返回一个合法的拓扑序数组；如果图里有环（不是 DAG），返回 null。

/**
 * Kahn 算法求拓扑序。
 * @param adj 邻接表：adj[u] = [u 指向的所有顶点]
 * @param n   顶点数量（编号 0..n-1）
 * @returns   一个合法的拓扑序；若图中有环则返回 null
 */
function kahnTopologicalSort(adj: number[][], n: number): number[] | null {
  // 1. 统计每个顶点的入度
  const indeg = new Array<number>(n).fill(0);
  for (let u = 0; u < n; u++) {
    for (const v of adj[u]) {
      indeg[v]++;
    }
  }

  // 2. 所有入度为 0 的顶点立刻入队
  const queue: number[] = [];
  for (let u = 0; u < n; u++) {
    if (indeg[u] === 0) queue.push(u);
  }

  const order: number[] = [];
  let head = 0; // 用下标模拟出队，避免 shift() 的 O(n) 开销

  // 3. 主循环：不断取出就绪顶点
  while (head < queue.length) {
    const u = queue[head++];
    order.push(u);

    for (const v of adj[u]) {
      indeg[v]--;            // v 少了一个前置
      if (indeg[v] === 0) {
        queue.push(v);       // 前置全部就绪，v 可以上场
      }
    }
  }

  // 4. 输出顶点数不足 n，说明剩余图中有环
  return order.length === n ? order : null;
}

代码总共不到三十行，但每个细节都有讲究。先看入度统计：这里用双重循环把邻接表扫一遍，每条边恰好贡献一次入度，所以统计阶段是 O(E)。再看入队初始化：把所有入度为 0 的顶点全部放进队列，一个都不能少。主循环里，我们用 head 指针模拟队头，queue 数组同时扮演队列存储；因为每次只从头部读、往尾部写，head 永远递增，出队操作是 O(1)，避免了 JavaScript 数组 shift() 方法删除头部元素时的 O(n) 搬移开销。这个”数组 + 头指针”的小技巧在算法题里非常常见，值得记住。

最后一行是点睛之笔：order.length === n 同时完成了”成功返回”和”环检测”两件事。如果图是 DAG，主循环必然能处理完所有顶点；如果图里有环，环上的顶点永远等不到入度归零，order 就会缺斤少两，此时返回 null，告诉调用方”这个图排不了”。具体的环检测原理我们在第 5 章展开，这里先记住结论。

如果顶点不是数字而是字符串（比如课程名、模块名），可以把数组换成 Map，或者先给每个字符串编号再跑算法。工程上最常见的做法是给字符串编号，因为数组访问比 Map 快得多，而且后续调试时打印编号对应的名字也很方便。下面是一个带名称映射的示例骨架，只展示关键差异：

function kahnWithNames(
  names: string[],
  adj: number[][]
): string[] | null {
  const n = names.length;
  const order = kahnTopologicalSort(adj, n);
  return order ? order.map((u) => names[u]) : null;
}

名字映射本身不改变算法，只是把编号翻译回人类可读的形式，但这一层翻译在生产环境里非常重要：构建系统报错时，开发者希望看到的是”模块 B 依赖模块 A”而不是”边 3 → 7 存在环”。

4.4 完整走查：一张图，六步排完

光看代码不够，我们来亲手走一遍。还是用第 3 章那张六顶点图：A → B、A → C、B → D、C → D、D → E、E → F。先把它的初始入度表算出来：A 没有边指向它，入度为 0；B 被 A 指向，入度 1；C 被 A 指向，入度 1；D 被 B 和 C 指向，入度 2；E 被 D 指向，入度 1；F 被 E 指向，入度 1。初始入度为 0 的顶点只有 A，所以队列初始化后是 [A]。

下面是每一步的完整状态表，建议对照着下面的状态图一起看：

步骤	取出	入队	输出序列	入度变化
初始化	—	A	（空）	B:1, C:1, D:2, E:1, F:1
1	A	B、C	A	B 1→0，C 1→0
2	B	—	A, B	D 2→1
3	C	D	A, B, C	D 1→0
4	D	E	A, B, C, D	E 1→0
5	E	F	A, B, C, D, E	F 1→0
6	F	—	A, B, C, D, E, F	全部排完

初始化：所有顶点都是白色，入度表为 A:0、B:1、C:1、D:2、E:1、F:1。A 是唯一就绪顶点，进入队列。

graph TD
    A["A"] --> B["B"]
    A --> C["C"]
    B --> D["D"]
    C --> D
    D --> E["E"]
    E --> F["F"]

第 1 步：取出 A，输出 [A]。遍历 A 的后继 B 和 C：B 的入度从 1 减到 0，C 的入度从 1 减到 0，于是 B、C 双双入队，队列变为 [B, C]。此时图中 A 已经”毕业”，B 和 C 拿到入场券。

graph TD
    A["A"] --> B["B"]
    A --> C["C"]
    B --> D["D"]
    C --> D
    D --> E["E"]
    E --> F["F"]
    classDef done fill:#3a3f5a,stroke:#888;
    class A done

第 2 步：队列头部是 B，取出 B，输出 [A, B]。B 的后继是 D：D 的入度从 2 减到 1，还没有归零，所以 D 不能入队。注意这里体现了”D 必须等两个人”的本质：走掉一个前置，D 还在等另一个。此时队列为 [C]。

graph TD
    A["A"] --> B["B"]
    A --> C["C"]
    B --> D["D"]
    C --> D
    D --> E["E"]
    E --> F["F"]
    classDef done fill:#3a3f5a,stroke:#888;
    class A,B done

第 3 步：取出 C，输出 [A, B, C]。C 的后继是 D：D 的入度从 1 减到 0，两位前置（B 和 C）全部到位，D 终于可以入场，队列变为 [D]。

graph TD
    A["A"] --> B["B"]
    A --> C["C"]
    B --> D["D"]
    C --> D
    D --> E["E"]
    E --> F["F"]
    classDef done fill:#3a3f5a,stroke:#888;
    class A,B,C done

第 4 步：取出 D，输出 [A, B, C, D]。D 的后继是 E：E 的入度从 1 减到 0，E 入队。此时整条链的中间环节全部打通，剩下的 E、F 是一段顺滑的流水线。

graph TD
    A["A"] --> B["B"]
    A --> C["C"]
    B --> D["D"]
    C --> D
    D --> E["E"]
    E --> F["F"]
    classDef done fill:#3a3f5a,stroke:#888;
    class A,B,C,D done

第 5 步：取出 E，输出 [A, B, C, D, E]。E 的后继是 F：F 的入度从 1 减到 0，F 入队。队列里只剩下最后一个顶点 F。

graph TD
    A["A"] --> B["B"]
    A --> C["C"]
    B --> D["D"]
    C --> D
    D --> E["E"]
    E --> F["F"]
    classDef done fill:#3a3f5a,stroke:#888;
    class A,B,C,D,E done

第 6 步：取出 F，输出 [A, B, C, D, E, F]。F 没有后继，队列为空，主循环结束。order 的长度是 6，等于顶点总数 V，算法宣告成功。把结果和原始图对照：A→B 满足（位置 1 在 2 前），A→C 满足（1 在 3 前），B→D 满足（2 在 4 前），C→D 满足（3 在 4 前），D→E 满足（4 在 5 前），E→F 满足（5 在 6 前），六条边全部从前向后，完美。

graph TD
    A["A"] --> B["B"]
    A --> C["C"]
    B --> D["D"]
    C --> D
    D --> E["E"]
    E --> F["F"]
    classDef done fill:#3a3f5a,stroke:#888;
    class A,B,C,D,E,F done

有一个细节值得回味：第 1 步结束后，B 和 C 同时在队列里，谁先出队决定了最终序列是 A→B→C→D→E→F 还是 A→C→B→D→E→F。我们在走查里按 FIFO 规则先取了 B，得到前一种；如果第 2 步先取 C，就会得到第 3 章画过的另一种合法序列。队列顺序只改变结果，不改变合法性——这正是拓扑排序不唯一性在算法层面的体现。

4.5 为什么 Kahn 算法一定正确？

写算法不能只靠”看起来对”，我们用一个不变量来证明。不变量：在每次循环开始前，队列里的每个顶点 u 都满足”u 的所有前置已经在输出序列 order 中”。

初始化时，入度为 0 的顶点本来就没有前置，不变量成立。假设循环开始时不变量成立，取出队首 u 并加入 order：因为 u 的前置全在 order 里，所以 order 中新增的 u 不会破坏任何边”前在后前”的性质（u 的前置都比 u 早，u 的后继都还没被处理、更不会出现在 u 前面）。接着对 u 的每个后继 v 减入度：v 在剩余图中的前置恰好少了一个（就是 u），所以当 indeg[v] 归零时，v 的所有前置确实都已进入 order，把 v 入队不会破坏不变量。归纳下去，order 在任意时刻都是一个合法的”部分拓扑序”：它的任意前缀都不会违反任何边。

还要证明算法不会提前终止、漏掉顶点。利用 2.3 节的引理一：在无环的剩余图中，只要还有顶点没被处理，就至少存在一个入度为 0 的顶点。入度为 0 意味着它要么从初始化起就在队列里，要么会在某个前置被处理时被推入队列；总而言之，只要剩余图非空且无环，队列就永远不会空。所以主循环必然持续到 order 包含全部 V 个顶点为止。只要输入是 DAG，Kahn 算法就一定能输出一个合法的完整拓扑序。

反过来，如果输入有环，环上的顶点永远不会入队：环上每个顶点的入度在剩余图中始终至少为 1（环本身贡献的边永远存在，除非环上某个顶点被处理，但环上顶点互相等待，一个都处理不了）。于是主循环会提前结束，order.length < V，我们据此判定”无解”。Kahn 算法同时完成了”求拓扑序”和”环检测”两件事，这是它最优雅的地方。

4.6 实现细节与常见变体

第一，入度统计和队列初始化都必须遍历完整张图。顶点 0 到 n-1 要全部扫到，包括孤立顶点：孤立顶点的入度为 0，会被直接放进队列，并在某个时刻被输出。如果漏扫了孤立点，order 长度不足，明明没有环却会被误判为有环。所以外层 for 循环不能只从”看起来像起点”的顶点开始。

第二，队列可以用数组加头指针实现，也可以用真正的 Queue 类。两者的区别只在”同一批就绪顶点的出场顺序”。用 FIFO 队列（先就绪先出）最直观；把数组当作栈用（push 和 pop，后进先出）也能得到合法拓扑序；用最小堆或优先队列则能保证”字典序最小”（第 8 章细说）。如果你在写前端工程代码，直接用一个真正的队列类或数组都行，只要保证出入队是 O(1) 摊销即可。

第三，小心重复边。如果输入数据里同一个依赖被重复声明（比如 A → B 出现两次），入度统计会把它算成 2。Kahn 算法本身对重复边依然正确：处理 A 时会把 B 的入度减两次，第一次减到 1 不入队，第二次减到 0 入队，B 仍然只入队一次，最终结果依然合法。但如果你为了节省空间去重了，结果也合法。换句话说，重复边不影响 Kahn 算法的正确性，只影响入度的绝对值，而算法只看”是否归零”。

第四，自环和多重环都会被自动发现。自环 A → A 会让 A 的入度至少为 1，且这条边永远无法被”移除”（移除它的唯一方式是处理 A，而 A 永远无法入队），所以 order 永远缺 A，算法返回 null。两顶点环 A → B → A 同理：A 入度 1、B 入度 1，谁都无法先归零。这就是为什么 Kahn 的环检测不需要任何额外代码——环会自己”堵死”自己。

第五，如果输入给的是边列表而不是邻接表，先花 O(E) 时间建邻接表即可。边的数量很大时（比如一百万条），注意邻接表的初始化要预先分配容量，避免反复扩容；在 JavaScript/TypeScript 里可以用 Array.from({ length: n }, () => [] as number[]) 一行建好。

5 环检测：Kahn 的顺带礼物

5.1 输出数量不足，就是有环

第 4 章的代码最后一行藏着一个小秘密：order.length === n 这个判断，就是一次完整的环检测。为什么？因为在 DAG 里，剥洋葱永远剥得完（2.3 节引理一保证剩余图总有入度为 0 的顶点）；而一旦图里有环，环上的顶点就陷入了一个”互相等待”的僵局：每个环上顶点的入度在剩余图里都至少为 1，因为环本身就贡献了一条永远无法被移除的边。于是主循环在某一步之后再也找不到入度为 0 的顶点，队列变空，循环提前结束，order 里缺的恰好就是环上（以及被环”拖累”的）顶点。

所以 Kahn 算法的环检测规则只有一句话：算法结束时，如果输出的顶点数少于顶点总数 n，则图里有环。 不需要额外维护 visited、不需要递归、不需要栈，环自己就把自己暴露了。更妙的是，Kahn 甚至能告诉你”至少哪些顶点有问题”：没有被输出的顶点集合，就是所有”永远无法就绪”的顶点，它们要么在环上，要么依赖环上的顶点。

这里有一个初学者容易犯的直觉错误：以为”队列空了”就等价于”有环”。其实队列空了也可能只是”这一批就绪顶点处理完了”，在无环图的正常执行中，队列也会周期性变空吗？让我们想想：在真正的 DAG 中，主循环结束只可能发生在 order 装满 n 个顶点之后，因为引理一保证只要还有剩余顶点，就一定有新的入度 0 顶点会被推入队列。所以”队列空 + order 没装满”才是有环的充要条件；“队列空 + order 装满”则是成功。把这两个条件拆开理解，就不会写出”队列一空就报错”的错误代码。

5.2 有环走查：看它怎么卡死

口说无凭，来走一个具体的例子。现在有四个顶点 A、B、C、D，边是：A → B、B → C、C → A，以及 D → B。也就是说，A、B、C 三人构成一个循环依赖，而 D 是 B 的前置、可以正常开工。

graph LR
    A["A"] --> B["B"]
    B --> C["C"]
    C --> A
    D["D"] --> B

先算初始入度：A 被 C 指向，入度 1；B 被 A 和 D 指向，入度 2；C 被 B 指向，入度 1；D 没有人指向它，入度 0。于是初始化队列为 [D]，output 为空。

第 1 步：取出 D，输出 [D]。D 的后继是 B：B 的入度从 2 减到 1，没有归零，B 不入队。此时队列为空，主循环结束。检查 order：长度是 1，而 n 是 4，1 < 4，于是算法宣布：图里有环。

graph LR
    A["A"] --> B["B"]
    B --> C["C"]
    C --> A
    D["D"] --> B
    classDef done fill:#3a3f5a,stroke:#888;
    class D done

剩下的三个顶点 A、B、C 为什么一个都排不出来？因为它们围成了一个环：A 等 B，B 等 C，C 等 A。D 被排掉之后，剩余图里只剩这个环，环上每个顶点的入度依然至少为 1（A 入度 1、B 入度 1、C 入度 1），没有一个顶点能先变成 0，于是队列永久为空。这个”卡死”的过程用表记录下来就是：

步骤	取出	输出	剩余图
初始化	—	（空）	A:1, B:2, C:1, D:0，队列 [D]
1	D	D	A:1, B:1, C:1，队列空，循环结束

注意 B 的入度在表中从 2 变成 1，但 1 不等于 0，所以 B 始终拿不到入场券。这就是环检测的完整机理：环上的每个顶点都欠着至少一个”环内前置”，而那个前置也欠着另一个环内顶点，于是谁都还不清这笔账。

5.3 与第 6 篇 DFS 三色检测呼应

第 6 篇我们学过的三色标记法，现在可以拿出来对比了。两者都能判断有向图是否有环，但检测机制完全不同：

• DFS 三色法：沿着递归路径走，遇到”灰色邻居”（还在当前递归栈上）就说明从那个灰色顶点能回到当前路径，构成环。它检测的是”递归过程中的回头路”，一次 DFS 就能给出具体的环路径。
• Kahn 法：从”入度为 0”的一端不断剥除顶点，剥不动了就说明剩下的是环。它检测的是”永远无法开工的顶点”，不需要递归，实现简单，但默认只能告诉你”有没有环、哪些顶点没被处理”，不直接告诉你环的具体边序列。

两种方法各有千秋。如果你只关心”能不能排、排出来是什么”，Kahn 算法一条龙搞定；如果你还要”指出环上的具体路径给用户看”（比如构建系统报错时要打印”检测到循环依赖：A → B → C → A”），那么三色标记法配合递归栈回溯更方便，因为它能在发现灰色邻居的瞬间，沿着栈把环上的顶点一个个捞出来。很多真实系统是两者混用的：先用 Kahn 做拓扑排序并顺手判环；一旦发现环，再对”未处理的子图”单独跑一次 DFS 三色法，把环路径精确打印出来。

flowchart LR
    Q{"要做什么？"} --> K["只需要拓扑序或判环"] --> Kahn["Kahn：入度剥除，输出不足即环"]
    Q --> P["需要输出环的具体路径"] --> DFS["DFS 三色：灰色邻居即环，沿栈回溯"]

还值得注意一个容易混淆的点：三色法检测的是”有向环”，而第 6 篇还讲过无向图的环检测（用父节点排除法）。无向图的环检测不能照搬三色法，因为无向图里一条边 A—B 会被 B 看到 A 已经访问过，必须额外排除父节点；有向图则没有这个问题，因为边有方向，A→B 和 B→A 是两回事。今天讨论的拓扑排序只适用于有向图，所以一律用有向环检测，别把无向图那套”排除父节点”的代码抄过来。

5.4 发现环之后怎么办

算法告诉你”有环”之后，工程上通常有三种处理方式。

第一种：直接报错并终止。 这是构建系统、包管理器最常见的做法。循环依赖意味着依赖图本身不合法，任何”聪明”的排序都无法拯救它，与其产出半成品，不如立刻失败，让开发者去改代码。报错信息越具体越好：最好能给出环上的顶点序列，甚至画出一条 ASCII 环图。

第二种：只对无环的部分排序。 如果业务允许”能排的先生成”，可以把 Kahn 输出的部分序列当作一个合法的部分顺序，把没被排出的顶点单独标记为”阻塞”或”待修复”。这在增量构建、容错调度里有价值：先构建不受环影响的部分，让系统部分可用，同时把环报告给负责人。

第三种：人工干预打破环。 在真实的软件工程里，循环依赖经常是设计缺陷，解决办法是重构：把环里某个依赖关系反转、拆出公共模块、用依赖注入延迟加载，等等。算法只能检测环，不能替你决定哪条边该断——那是人的决策。但至少，有了环检测，你永远不用在”为什么构建卡死”这种问题上靠猜。

6 DFS 后序写法：完成时间倒过来

6.1 一个不起眼的观察

Kahn 算法是从”入度”这一端出发的自底向上思路。拓扑排序还有另一种同样经典的写法：先用 DFS 求出所有顶点的后序（postorder），再把它整个倒过来。 我们在第 5 篇详细学过：前序是”进入顶点时记录”，后序是”离开顶点时记录”，也就是等某个顶点的所有后代都访问完之后，才把这个顶点自己记下来。后序列表的完整含义是：顶点按完成时间从早到晚排列——先完成的在前，最后完成的在最后。

现在抛出一个关键观察：如果图是 DAG，那么后序的逆序恰好是一个合法的拓扑序。也就是说，DFS 拓扑排序一共只有两行核心逻辑：一行是”完成时把顶点压入数组”，另一行是”最后把数组反转”。听起来简单得不可思议，但它背后有一个非常深刻的理由，值得花一整节讲清楚。

6.2 为什么后序的逆序就是拓扑序？

要证明”逆序后序是拓扑序”，只需要证明一件事：对图中任意一条边 u → v，v 一定比 u 先完成。 因为如果 v 先完成，那么后序列表里 v 排在 u 前面，反转之后 u 就排在 v 前面，恰好满足”每条边的起点在终点之前”。

那么”v 一定比 u 先完成”为什么成立？我们盯住 DFS 第一次访问 u 的时刻，那一刻 u 开始探索它的所有邻居，其中就包括 v。此时 v 处于三种状态之一：

情况一：v 还是白色（完全没访问过）。 那么 DFS 会立刻进入 v，把 v 所在的整棵子树全部探索完，然后 v 先完成，之后控制权才回到 u 身上继续探索下一个邻居，最后 u 才完成。所以 finish(v) < finish(u)，结论成立。注意这里还隐藏了一个信息：在 DAG 里，边 u→v 意味着 v 的完成时间一定早于 u，不管这条边是”树枝边”（v 是 u 的子树后代）还是”横叉边”（v 在别处已经访问过）。 树枝边显然成立；横叉边对应下面第二种情况。

情况二：v 是黑色（已经完成）。 这发生在 u 的另一个邻居（或之前的外层循环）已经把 v 探索完的情况下。v 既然已经完成，自然 finish(v) < finish(u)（因为 u 此刻还没完成），结论依然成立。DAG 里这种情况对应”从 u 搭到一片已经完工的区域”的横叉边或前向边，完全合法。

情况三：v 是灰色（正在递归栈上）。 这意味着 u 是在 v 的某次递归深处被访问到的，也就是说存在一条从 v 出发、经过若干顶点、最后到达 u 的路径，而 u 又有一条边指向 v，合起来 v → … → u → v 就是一个环。但我们现在假设图是 DAG，所以这种情况不可能发生。换句话说，三色标记里唯一会破坏结论的情形，恰好就是”图里有环”的情形——这就是为什么 DFS 拓扑排序天然内置了环检测：如果在 DFS 过程中看到灰色邻居，直接宣布无解。

把三种情况合并，就得到了严格的结论：在 DAG 中，任何边 u→v 都满足 finish(v) < finish(u)，所以后序列表的逆序满足”每条边的起点都在终点前面”，是一个合法的拓扑序。这个证明和第 6 篇的三色标记几乎共用同一套语言，你可以把今天的内容理解成”三色标记顺便把拓扑排序也做了”。

用图来感受一下。还是那六顶点主图，假设 DFS 从 A 出发、邻居顺序是 B 在前 C 在后，那么递归会一路钻到 F，然后层层返回，最后再访问 C。括号里的数字是每个顶点的完成顺序（1 表示最先完成）：

graph TD
    A["A（完成 6）"] --> B["B（完成 4）"]
    B --> D["D（完成 3）"]
    D --> E["E（完成 2）"]
    E --> F["F（完成 1）"]
    A --> C["C（完成 5）"]
    C -. "访问 D 时发现已完工" .-> D

后序列表按完成时间从早到晚写出来是：F、E、D、B、C、A。把它整个倒过来：A、C、B、D、E、F。逐条边检查：A→B（1 在 3 前）、A→C（1 在 2 前）、B→D（3 在 4 前）、C→D（2 在 4 前）、D→E（4 在 5 前）、E→F（5 在 6 前），全部满足。注意这个结果和 Kahn 的 A→B→C→D→E→F 不同（C 和 B 换了位置），但它同样合法——又一次印证了拓扑序不唯一。

flowchart LR
    Post["DFS 后序：F → E → D → B → C → A"] --> Rev["整体反转：A → C → B → D → E → F"]

6.3 TypeScript 实现

代码几乎是把第 6 篇的三色标记照抄一遍，只加了一行”完成时记录”：

/**
 * DFS 后序写法求拓扑序。
 * @param adj 邻接表
 * @param n   顶点数量
 * @returns   合法的拓扑序；图中有环则返回 null
 */
function topologicalSortByDFS(adj: number[][], n: number): number[] | null {
  const color = new Array<number>(n).fill(0); // 0 白（未访问），1 灰（栈上），2 黑（完成）
  const postorder: number[] = [];
  let hasCycle = false;

  function dfs(u: number): void {
    color[u] = 1; // 进入 u：染灰
    for (const v of adj[u]) {
      if (color[v] === 1) {
        hasCycle = true; // 灰色邻居 = 环
        return;
      }
      if (color[v] === 0) {
        dfs(v);
      }
    }
    color[u] = 2;      // 离开 u：染黑
    postorder.push(u); // 后序：完成时记录
  }

  for (let u = 0; u < n; u++) {
    if (color[u] === 0) dfs(u);
  }

  if (hasCycle) return null;
  return postorder.reverse(); // 后序倒序 = 拓扑序
}

三个细节要说明。第一，外层 for 循环保证图不连通时也能覆盖所有分量，这和第 6 篇的框架完全一致；第二，一旦发现环，我们立刻把 hasCycle 置为 true 并返回，此时递归栈上可能还有一些灰点没走完，但因为最终结果会是 null，这些中间状态无所谓；第三，后序数组用 push 收集、最后一次性 reverse，而不是每次 unshift（把新元素插到头部），因为 unshift 是 O(n) 操作，会让总复杂度退化到 O(V²)。这个性能细节在 V 很大时是生死攸关的。

如果担心递归深度（比如图是一条一万个顶点的链），可以把递归改成显式栈模拟，或者干脆用 Kahn 算法。工程上有一个朴素的选型建议：图小、追求可读性，用 DFS 后序；图大、怕栈溢出，用 Kahn。 两种算法的时间复杂度相同，正确性相同，差别主要在于代码风格和递归风险。

6.4 Kahn 与 DFS：两种写法对比

两种算法都能在 O(V+E) 时间内完成拓扑排序并检测有向环，但性格完全不同。把它们的差异整理成一张对照表：

维度	Kahn 算法	DFS 后序写法
核心思想	入度归零者优先，剥洋葱	完成时间倒序，回溯时记录
主要数据结构	入度表 + 队列	三色数组 + 递归栈
是否递归	否，天然迭代	是（也可改显式栈）
环检测方式	输出数 < n	遇到灰色邻居
能否直接输出环路径	不能，需要辅助 DFS	能，沿递归栈回溯
输出顺序风格	取决于队列选择（FIFO/LIFO/优先队列）	取决于邻居遍历顺序
实现难度	略简单，无递归	略复杂，但代码对称优雅
风险点	漏掉初始化入队顶点	递归栈溢出、unshift 误用

这张表最后两行值得多说一句：Kahn 的风险是”初始化时漏入队”，一旦漏了，明明无环也会被判成有环；DFS 的风险是”递归深度”和”后序收集方式”。两个算法写对之后的结果都正确，但各自的小坑完全不同，建议两个都亲手实现一遍，面试时才能游刃有余。

7 复杂度与应用：拓扑排序养活了多少系统

7.1 复杂度：O(V+E)，图算法的黄金标准

先算 Kahn 算法的时间复杂度，一步一步来。第一阶段是统计入度：外层循环遍历所有顶点的邻接表，每条边恰好被访问一次，耗时 O(E)。第二阶段是队列初始化：扫描一遍顶点数组，把入度为 0 的顶点全部入队，耗时 O(V)。第三阶段是主循环：每个顶点只会出队一次（因为只有入度归零的那一次会被推入队列），所以出队操作总计 O(V)；对每个出队顶点 u，我们遍历它的整条邻接表，把所有边又扫了一遍，总计 O(E)。三个阶段加起来是 O(V + E)。这就是拓扑排序的时间复杂度，也是图算法里能拿到的最好量级——因为任何算法至少要把每条边读一遍才能知道依赖关系，O(V+E) 已经是”理论下限附近”。

空间复杂度同样是 O(V)：入度表是长度为 V 的数组，队列最坏情况下可能同时装下所有顶点（比如一个完全独立、没有边的图），输出序列也是 V 的长度，三者加起来仍然是 O(V) 量级。DFS 后序版本的空间也差不多：三色数组 O(V)、后序数组 O(V)、递归栈最坏 O(V)（一条链状图会让递归深度达到 V），总空间 O(V)。值得一提的是，如果图是用邻接矩阵存储的，遍历所有边需要扫描整个矩阵，复杂度会变成 O(V²)，所以做拓扑排序时请优先使用邻接表。

还有一个常被忽略的点：拓扑排序的 O(V+E) 是”对整张图跑一遍”的复杂度。如果只需要”某个前置顶点是否先于某个后置顶点”，直接跑一遍拓扑排序得到全序，然后用下标比较即可；如果图会动态增删边，每次重新排序代价就高了，这时才需要考虑增量维护（比如记录每个顶点当前层数、只重排受影响的部分），但这已经属于高级话题，不在今天的范围内。

7.2 应用一：课程表

课程表是拓扑排序最著名的招牌应用，也是 LeetCode 第 207 题”课程表”和第 210 题”课程表 II”的原型。题目输入通常是一个课程数量 numCourses 和一个前置关系数组 prerequisites，其中 prerequisites[i] = [a, b] 表示”想学 a 必须先学 b”，也就是一条从 b 指向 a 的边。第 207 题只问”能不能学完所有课程”（等价于问图是不是 DAG），第 210 题直接要求输出一种选课顺序（就是拓扑序）。

用 Kahn 算法解决课程表问题时，注意方向约定：把 b → a 建边，然后统计入度。如果返回的 order 长度等于课程总数，说明可以学完；否则说明课程依赖中存在环（比如”想学 A 必须先学 B，想学 B 必须先学 A”，两个课程互相卡死）。真实排课系统还会在拓扑序之上加约束：比如每学期最多修六门课、有些课只在秋季开设、有些课有推荐学期区间。这时拓扑排序负责生成”依赖上合法的序列”，而排课器再在这个序列上做约束规划，把并行课程分到不同的学期。同一个拓扑序里的顶点彼此没有依赖关系，天然可以并行——这就是”分层拓扑排序”（按轮次取出所有入度为 0 的顶点）在排课调度里的价值：每一轮的所有课程可以同时修，轮数就是最短总学期数。

graph LR
    P["程序设计"] --> D["数据结构"]
    D --> A["算法分析"]
    M["微积分"] --> L["线性代数"]
    L --> S["概率论"]
    D --> M["机器学习导论"]
    L --> M

上面这张扩展版选课图里，算法分析依赖数据结构，机器学习导论同时依赖数据结构与线性代数。拓扑排序会输出类似”程序设计、微积分、数据结构、线性代数、算法分析、概率论、机器学习导论”的顺序；而分层版本会在第一轮输出”程序设计、微积分”，第二轮输出”数据结构、线性代数”，第三轮输出”算法分析、概率论、机器学习导论”，告诉你最短需要三个学期。注意第三轮的”概率论”和”机器学习导论”互不依赖，可以并行，这正是拓扑排序给调度系统带来的自由度。

7.3 应用二：构建系统（Make 与 webpack）

构建系统是拓扑排序在工程界最忠实的客户。以经典工具 Make 为例：Makefile 里写着一个个”目标”以及它们依赖的文件或其他目标，比如”可执行文件依赖一堆 .o 文件，每个 .o 文件依赖对应的 .c 源文件”。Make 把这些目标与依赖关系建成一张有向图，然后做一次拓扑排序，就知道应该先编译哪个、后链接哪个。如果用户执行 make -j8，Make 还会把”当前没有未完成依赖”的目标并行启动，同一时间最多跑八个任务——它的并行调度器本质就是在拓扑序上不断挑选就绪任务。

graph LR
    A["main.c"] --> O1["main.o"]
    B["util.c"] --> O2["util.o"]
    C["math.c"] --> O3["math.o"]
    O1 --> EXE["app 可执行文件"]
    O2 --> EXE
    O3 --> EXE
    H["common.h"] --> O1
    H --> O2
    H --> O3

上图里，三个源文件各自编译成目标文件（它们互不依赖，可以并行），等三个目标文件全部就绪后，链接器才能把它们拼成可执行文件；同时 common.h 被三个源文件共同包含，任何一个源文件重编后，依赖它的目标文件都要重编。这张图是一个教科书级的 DAG：编译阶段宽、链接阶段窄，拓扑排序会先输出三个 .o 再输出 app。

前端构建工具同样离不开拓扑排序。webpack 把每个模块看成一个节点，把 import/require 关系看成有向边，构建时按依赖顺序打包，保证被依赖的模块先被处理、先被输出。webpack 的循环依赖警告（Circular Dependency）正是对图做环检测后的产物：虽然现代浏览器和打包器通常能容忍循环 import（运行时才真正取值），但循环依赖会破坏模块的初始化顺序，造成”拿到 undefined”的经典 bug，所以工具宁可警告也不沉默。还有一类任务流构建系统（比如 GitHub Actions 的 job 依赖、CI 流水线、数据库迁移工具）也全是同一个套路：声明依赖，自动排序，能并行就并行。

7.4 应用三：包管理器

npm、yarn、pnpm 这些包管理器每天都在做拓扑排序：每个包声明自己的 dependencies，包与包之间形成依赖图。安装时，包管理器先解析出完整的依赖树（或者依赖图），做环检测，然后按拓扑序决定安装先后：先装没有任何依赖的底层包，再装依赖它们的上层包。为什么顺序这么重要？因为包的安装脚本（postinstall）可能需要依赖包已经就位；更重要的是，node_modules 里的符号链接和扁平化布局依赖”父依赖先存在”，否则链接会指向不存在的目录。

graph LR
    L["lodash"] --> A["业务工具库"]
    L --> R["React"]
    R --> U["UI 组件库"]
    A --> U
    U --> App["应用入口"]

在这张简化的依赖图里，lodash 谁都不依赖，最先安装；React 依赖 lodash，业务工具库也依赖 lodash，两者并列第二；UI 组件库等 React 和业务工具库都装好后再装；应用入口最后装。如果 lodash 的某个版本和 React 需要的版本冲突，解析器还要先做版本选择（挑出一个同时满足约束的版本），再进入安装排序阶段——版本解析是另一层问题，但一旦版本定下来，安装顺序就是标准的拓扑排序。

值得一说的是，环检测对包管理器不是”可选优化”，而是安全底线。历史上很多著名的依赖事故都源于循环依赖：两个包互相依赖时，安装脚本可能因为”对方还没装好”而执行失败，或者运行时代码拿到对方未初始化的导出。npm 在解析阶段发现循环依赖时会打警告甚至报错；pnpm 则会在严格模式下拒绝安装循环依赖。算法层面它们用的就是今天学的两种方法之一：Kahn 剥不动了，或者 DFS 看到灰色邻居了。

7.5 应用四：编译器

编译器内部几乎处处是 DAG。先看”编译单元顺序”：C/C++ 项目里，一个 .c 文件包含的头文件如果依赖另一个头文件生成的产物，编译顺序就不能乱；虽然现代构建系统通常按文件系统级依赖处理，但底层的排序逻辑依然是拓扑排序。再看链接器：静态库之间的符号依赖有方向（库 A 的某个目标文件需要库 B 的符号），链接器必须按依赖顺序排列库，否则会报”未定义符号”。GNU ld 支持 --start-group 之类的机制来容忍环，但那是在用蛮力弥补依赖图的缺陷，正常情况下的正确姿势就是拓扑序。

更深刻的应用在中间代码优化里。编译器把程序表示成控制流图（CFG），每个基本块是一段顺序执行的指令序列，基本块之间用跳转边相连。很多优化（死代码消除、常量传播、活跃变量分析）都需要按控制流的拓扑序或逆拓扑序遍历基本块：正向数据流分析按拓扑序传播信息，反向分析按逆拓扑序传播。为什么？因为”信息沿依赖方向流动”的语义和拓扑排序完全一致——只有前驱的信息先算出来，后继的信息才算得准。

graph TD
    B1["入口基本块"] --> B2["条件分支"]
    B2 --> B3["真分支"]
    B2 --> B4["假分支"]
    B3 --> B5["汇合点"]
    B4 --> B5
    B5 --> B6["出口基本块"]

上图是一个典型控制流图。注意控制流图本身可以有环（循环结构会让 CFG 含环），所以编译器做数据流分析时处理环的策略是”迭代到不动点”，而不是简单跑一遍拓扑排序；但无环部分（前向边、退出路径）依然按拓扑序处理，环则用不动点迭代收敛。这正是拓扑排序在真实系统里的常态：它常常作为”无环子图上的高效遍历顺序”被嵌入更大的算法中，而不是孤立地跑一次就完事。

7.6 应用五：数据流分析、任务编排与更多

数据流分析是编译器优化和静态分析的核心技术，而”按依赖顺序传播信息”是它的骨架。以”到达定值”（reaching definitions）分析为例：每个基本块的入口处”哪些变量的定义可能到达这里”取决于前驱基本块的出口信息，信息沿 CFG 的边向前流动。对无环的 CFG，一次拓扑序遍历就能得到精确结果；对带环的 CFG，则需要反复迭代直到信息不再变化。同样的模式出现在活动变量分析、可用表达式分析、常量传播等几乎所有经典数据流分析里，所以编译器教科书里几乎都会先讲拓扑排序再讲数据流。

离开编译器，拓扑排序的足迹遍布整个软件栈：Spark 把用户的计算逻辑翻译成 DAG 然后调度执行，DAG 调度器（DAGScheduler）这个命名就说明了一切；Airflow、Temporal 之类的任务编排系统让用户声明任务依赖，引擎按拓扑序派发；数据库迁移工具（比如 Rails 的 ActiveRecord Migrations 按版本号排序，Flyway 依赖链）也用它保证先建表再插外键；依赖注入容器要按依赖顺序构造对象；甚至装修队安排工序（先水电后泥瓦、先泥瓦后木工）本质都是同一道题。

flowchart LR
    JobA["拉取数据"] --> JobB["清洗数据"]
    JobB --> JobD["训练模型"]
    JobC["标注数据"] --> JobD
    JobD --> JobE["评估并发布"]

这张数据流水线图展示了四个任务的依赖：拉取与标注可以并行，清洗等拉取完成，训练等清洗和标注都完成，最后评估发布。真实调度器会把它转成拓扑序，并在每一层并行执行可并行的任务，让整条流水线在”满足所有依赖”的前提下尽量短。你可以试着用 Kahn 算法手算它的拓扑序：第一轮就绪的是”拉取数据”和”标注数据”两个任务，接下来的顺序就一目了然了。

7.7 进阶：分层拓扑排序与并行调度

普通拓扑排序只回答”存在什么顺序”，而真实系统往往还想知道另一件事：如果允许并行，最快需要几轮才能全部完成？ 这就要用到分层（按轮次）的 Kahn 算法：每一轮先把当前所有入度为 0 的顶点一次性取出，作为同一层；它们之间互不依赖，理论上可以并行执行；取完之后统一更新入度，下一轮再取新就绪的顶点。这样得到的”层数”就是完成全部任务所需的最少轮数，每一层的顶点集合就是”可以同时开工”的候选集。

还是拿第 7.2 节的扩展选课图举例：第一轮就绪的是”程序设计”和”微积分”（入度都是 0）；把它们取走后，“数据结构”和”线性代数”的入度归零，成为第二轮；第二轮结束，“算法分析”、“概率论”、“机器学习导论”全部就绪，成为第三轮。三层就是最短学习轮数——只要学校允许一个学期修任意多门课，三个学期一定学得完，两个学期一定学不完。并行构建同理：make -j 的每一波并行任务，本质上就是分层拓扑序的一层；CI 流水线的 stage 并行、Spark 的 stage 划分，也都是这个思想的工程化。

flowchart LR
    L1["第 1 层：程序设计、微积分"] --> L2["第 2 层：数据结构、线性代数"]
    L2 --> L3["第 3 层：算法分析、概率论、机器学习导论"]

分层拓扑排序还有两个实用变体。其一是关键路径：在任务带权（每个任务需要不同的执行时长）的 DAG 上，最长路径的长度决定了整条流水线的最短完工时间，这条最长路径就叫关键路径；求它的标准做法就是先拓扑排序，再按拓扑序做动态规划（relax 每个后继的最长完成时间）。其二是DAG 上的动态规划：因为拓扑序保证”前置永远先于后置”，很多 DP（最长路径、最短路径、方案计数、期望值）都可以沿着拓扑序一遍算完，每到一个顶点时它依赖的状态必然已经算好。第 8 篇会看到这个套路用在 DAG 最短路径上——届时你一定会感谢今天这个”顺序先于状态”的直觉。

flowchart TD
    A["任务 1（2 天）"] --> B["任务 3（3 天）"]
    A --> C["任务 4（1 天）"]
    C --> D["任务 5（4 天）"]
    B --> D
    D --> E["任务 6（2 天）"]

上面这张带权 DAG 里，每个任务标了工期。从任务 1 到任务 6 有三条路径：1→3→6、1→4→5→6、1→3→5→6（如果 3 和 5 之间有边的话），其中最长的一条决定了最短完工时间。你可以试着把每条路径的工期加起来，再对照”按拓扑序做 DP”的方法，看结果是否一致——这就是关键路径分析的一堂课。

8 常见问题：多解、部分排序与经典坑

8.1 想要字典序最小的拓扑序？换一个容器

拓扑排序的多解问题在实际需求里经常会变成”请输出字典序最小的那个”。比如课程表系统希望”在同样合法的方案里，课程编号小的尽量先排”，这样输出更稳定、更可预测。解决办法只有一句话：把 Kahn 算法里的普通队列换成优先队列（最小堆），每次弹出编号最小的就绪顶点即可。

为什么这样贪心是正确的？因为”字典序最小”只要求每一步选择当前可选的顶点里最小的那一个。Kahn 算法的合法性只依赖”被弹出的顶点入度为 0”这个条件，不依赖弹出了谁；所以每一步选择最小的合法顶点，既不会堵死后续选择（就绪集合只会随着处理变大，不会因为选了小的而变小），又能保证最终序列的字典序最小。这个证明思路和”每次挑最小的可行任务”的贪心模板完全一致。

// 伪代码：只展示与普通队列版本的关键差异
const heap = new MinHeap<number>(); // 最小堆，按顶点编号比较
for (let u = 0; u < n; u++) {
  if (indeg[u] === 0) heap.push(u);
}
while (!heap.isEmpty()) {
  const u = heap.pop()!;        // 每次取出当前最小的就绪顶点
  order.push(u);
  for (const v of adj[u]) {
    if (--indeg[v] === 0) heap.push(v);
  }
}

用最小堆替换队列后，时间复杂度从 O(V+E) 变成 O(V log V + E)，因为每次堆操作是 O(log V)。如果要求不是”字典序最小”而是”某个关键任务尽量靠前”，可以把比较器换成自定义优先级（比如紧急任务的编号映射成更小的权重），思路完全一样。注意：用普通队列”先就绪先出”得到的序列不一定是字典序最小的，哪怕就绪顺序碰巧看起来有序。比如第 4 章例子里，A 之后 B、C 同时就绪，队列按就绪顺序给出 A→B→C→D→E→F，这恰好是字典序最小；但如果邻接表顺序不同、或者 B 和 C 的就绪顺序反过来，普通队列就会给出 A→C→B→D→E→F，而字典序最小解依然是 A→B→C→D→E→F。所以”想要字典序最小”必须显式换容器，不能指望运气。

8.2 只有部分顶点能排出来，怎么办？

“只能排出一部分顶点”只有一种根本原因：剩余顶点所在的子图里有环（或者说，这些顶点的依赖闭包里包含环）。图不连通不会导致部分排序——多个分量可以分别排序后拼在一起；孤立点也会被正常排入。真正卡住 Kahn 算法的永远是环：环上的顶点互相等待，而依赖环的顶点即使本身不在环上，也因为”等一个永远就绪不了的环上顶点”而无法输出。

遇到这种情况，工程上按以下四步处理：

1. 把已经输出的 order 当作一个合法的部分拓扑序收下。 它满足”其中任意一条边都从前到后”，对没有环的部分是完全正确的排序。
2. 把未输出的顶点集合 U 找出来。 U 里的顶点要么在环上，要么被环依赖链拖住。对 U 构成的诱导子图再跑一次 DFS 三色法，找到具体的环路径，生成精确的报错信息。
3. 决定系统行为：严格模式直接失败；容错模式先构建无环部分，把 U 标记为”阻塞”，等人工修复依赖后再增量重排。
4. 修复依赖：拆环、加公共模块、反转依赖方向或使用延迟加载，然后重新跑拓扑排序验证。

还有一类更刁钻的题目：“我不想输出完整序列，只想知道顶点 x 和 y 谁必须先做？” 如果 x 能到达 y，那么 x 必须在 y 前；如果 y 能到达 x，反过来；如果两者互不可达，则它们的顺序自由。这个判断用一次 DFS/BFS 从 x 出发做可达性检查即可，甚至不必做完整拓扑排序。可见”拓扑排序”和”可达性”是一对互补工具：前者回答”存在一个什么样的全局顺序”，后者回答”某两个顶点之间有没有强制顺序”。

flowchart TD
    Start["跑 Kahn"] --> Check{"order 长度 == V？"}
    Check -- "是" --> OK["输出完整拓扑序"]
    Check -- "否" --> Part["保留部分序，标记未输出集合"]
    Part --> Dfs["对未输出子图跑 DFS 三色"]
    Dfs --> Report["输出环路径 + 阻塞清单"]

8.3 六个经典坑，逐个排雷

坑一：把边的方向建反。 有人习惯把”依赖关系”建成”后置指向前置”，然后整个算法就反了。写代码前先给自己立一个约定，比如”u → v 表示 u 必须先于 v”，并写进注释，最好再加一个两三行的手算用例做冒烟测试。

坑二：初始化队列时漏掉顶点。 常见于只从”看起来像起点”的顶点入队，或者忘了处理编号不连续/孤立顶点。Kahn 的初始化必须扫描全部 V 个顶点，一个都不能少。

坑三：用 shift() 当队列出队。 JavaScript 数组的 shift() 会把剩余元素整体前移，一次 O(n)，总复杂度退化成 O(V²)。用 head 指针模拟队头，或者用真正的队列实现。

坑四：把无向图环检测的逻辑搬过来。 无向图要排除父节点，有向图不需要；有向图要看灰色邻居，无向图那套”已访问且非父”会漏判方向。两者别混用。

坑五：以为拓扑序唯一。 只要存在不可比较的顶点对，就有多个合法序列。面试时如果被问”这个图有几个拓扑序”，先找出所有”不可比较对”，再小心计数；如果被问”输出一个”，任何合法序列都算对。

坑六：DFS 后序收集用了 unshift。 每次在数组头部插入是 O(n)，总时间变成 O(V²)；正确做法是 push 收集后整体 reverse。这个坑隐蔽在”代码看起来也能跑”里，图一大就现出原形。

9 速查表：一页复习拓扑排序

把今天的内容压缩成两张表。第一张是核心概念与算法对比：

项目	Kahn 算法	DFS 后序写法
适用条件	有向无环图（DAG）	有向无环图（DAG）
时间	O(V+E)	O(V+E)
空间	O(V)	O(V)
核心	入度表 + 队列	三色数组 + 递归栈
就绪判定	入度归零	灰色邻居判环，黑色后记录
输出	队列弹出顺序	后序反转
环检测	order.length < n	发现灰色邻居
字典序最小	队列换最小堆	需要额外处理，通常用 Kahn

第二张表是常见问题的一句话答案：

问题	一句话答案
什么是拓扑排序？	把 DAG 顶点排成一行，使所有边都从前到后
什么样的图有拓扑序？	有向无环图（DAG），有环必然无解
拓扑序唯一吗？	不一定，不可比较的顶点对可以互换
Kahn 怎么判环？	输出顶点数少于 V 就有环
DFS 怎么写？	完成后序列表，整体反转即拓扑序
要字典序最小？	Kahn 的队列换成最小堆
只有部分顶点能排？	剩余子图有环，保留部分序并报告环

最后用一句话串起全篇：依赖关系建模成有向边，环是死锁，拓扑排序是合法的线性顺序，Kahn 从入度 0 剥起，DFS 把完成时间倒过来，两个算法都在 O(V+E) 内同时完成排序与环检测。 把这句话刻在脑子里，比背任何代码都有用。

10 自测题：练完才算学会

11 下一篇预告

下一站，我们进入图系列最实用、最常考的主题之一：《图系列第 8 篇：最短路径——从 BFS 到 Dijkstra》。

今天学的拓扑排序会在第 8 篇里以意想不到的方式再次登场：在 DAG 上求最短路径，可以先用拓扑排序确定遍历顺序，然后沿着拓扑序做一次简单的动态规划，就能处理**任意边权（包括负数）**的最短路径——这是 Dijkstra 都做不到的。而第 4 篇的 BFS 则是无权图的最短路径利器，第 8 篇会从它讲起，逐步过渡到带权图的 Dijkstra 算法：优先队列、松弛操作、负权边为什么会让 Dijkstra 翻车，以及 Bellman-Ford 如何收拾残局。

到时你会看到，导航软件怎么在几百万条道路里快速找到最短路线、游戏里寻路用的 A* 和 Dijkstra 是什么关系、网络路由协议凭什么相信邻居转发的”距离信息”。最短路径是图论的”高速公路”，而今天你手里的拓扑排序，正是通往它的第一张路条。我们第 8 篇见！