第 13 章　最短路径与拓扑排序

本章解决的问题：怎么把一堆"谁必须先做"的任务排成一个合法顺序？以及"从 A 到 B 最近怎么走" —— 为什么边权的条件一变，就得换一套算法？

13.1　拓扑排序与依赖解析

学习目标：学完本节，你能

• 说清什么叫拓扑序，并判断一个序列是否合法；
• 用 Kahn 算法（入度 + 队列）写出拓扑排序，并用它检测环；
• 用 DFS 后序取逆写出另一种拓扑排序，并说清"为什么必须反转"；
• 说出"Kahn 剩下的顶点"和"环上的顶点"不是一回事。

先修：12.4（有向图环检测、三色标记）、12.2（DFS）、5.2（队列）。 固定术语：拓扑排序（Topological Sort）、入度（In-Degree）、环检测。 环境与版本：.NET 8 / C# 12。 预计阅读：32 分钟。

一、直觉：一个上线事故

小陈所在的公司有一套微服务。 上线脚本按固定顺序逐个启动：gateway, user-service, order-service, config-center, db-proxy。

上线那天 gateway 直接崩了 —— 它启动时要连 config-center 拉配置，而后者排在它后面；让 order-service 先起？它依赖 db-proxy，也不行。

小陈最后把脚本改成了"按依赖关系排序" —— 不是按字母、不是按重要性，而是按"谁必须先于谁"。

这就是拓扑排序：给定一堆"必须先做 A 才能做 B"的约束，把它们排成线性顺序，使每条约束都被满足。生活中的例子到处都是：

这些问题长得完全一样。 学一次，通吃。

二、形式化：DAG 与拓扑序

建模规则：A 依赖 B，就画一条 $B \to A$ 的边（B 先做，A 后做）。

方向很重要：画反了，后面所有算法都会给出倒过来的结果 —— 这是新手最常犯的错。

这样得到的图必然有向、且无环 —— 因为"循环依赖"根本无法执行，它有专门的名字：有向无环图（Directed Acyclic Graph，DAG）。如果出现了环（A 等 B、B 等 C、C 又等 A），谁都动不了 —— 这不是"顺序没排好"，而是系统根本跑不起来。

拓扑排序（Topological Sort）：把 DAG 的所有顶点排成一个线性序列，使得对于图中的每一条边 $(u, v)$，$u$ 都排在 $v$ 的前面。

换句话说：所有的边都"从前往后指"，没有一条"往回指"。

举个具体例子。 8 门课的依赖关系：

  高等数学 ──> 线性代数 ──┐
      │                   ├──> 数据结构 ──> 算法分析 ──┐
      └────> 程序设计基础 ─┘         │                 ├──> 编译原理
                    │               └──> 操作系统 ────┘
                    └────────────────────> 计算机网络

一个合法的拓扑序是：

  高等数学 → 线性代数 → 程序设计基础 → 数据结构 → 操作系统 → 算法分析 → 计算机网络 → 编译原理

验证方法：逐条检查边，看起点是不是都排在终点前面 —— 九条边全部满足 ✓

关键点：拓扑序通常不唯一

同一张课表，下面这个顺序也完全合法：

  高等数学 → 程序设计基础 → 线性代数 → 数据结构 → 操作系统 → 算法分析 → 编译原理 → 计算机网络

因为"线性代数"和"程序设计基础"之间没有边 —— 谁先谁后都行。这是拓扑排序和普通排序最大的区别：第 7、8 章的排序结果唯一，拓扑排序的结果通常有很多个 —— 题目问"拓扑序"时，答案是一个集合。

那"存在性"唯一吗？

定理：一个有向图存在拓扑序，当且仅当它没有环。

有环 ⇒ 矛盾：设环是 $v_1 \to \dots \to v_k \to v_1$，拓扑序要求 $v_1$ 在 $v_2$ 前、……、$v_k$ 在 $v_1$ 前，合并起来就是"$v_1$ 必须排在自己前面"。无环 ⇒ 有拓扑序：Kahn 能跑完就说明了存在性（下一节）。

用法："能不能拓扑排序"和"有没有环"是同一个问题 —— 拓扑排序天然带一个副产品：环检测（12.4 节用三色标记做过，本节会看到第二种方法）。

三、Kahn 算法：从"没有前置依赖"的地方开始

先想一个朴素的问题：哪门课现在就能上？答案是所有先修课都已上完的课 —— 一开始就是入度为 0 的课。

入度（In-Degree）：指向该顶点的边数。在本节约定下（边 $B \to A$ 表示 B 先做、A 后做），入度 = 前置条件的个数：为 0 表示现在就能做，> 0 表示还有前置条件没完成。

Kahn 的思路一句话：反复找出"入度为 0"的顶点，输出它，然后把它从图里"删掉"（让所有邻居入度减 1） —— 这样邻居的前置条件就少一个，减到 0 时它也就"能做"了。

完整步骤：

  1. 统计所有顶点的入度
  2. 把所有入度为 0 的顶点放进队列
  3. 当队列不空时：
       a. 出队一个顶点 v，加入结果序列
       b. 对 v 的每一个邻居 next：
            入度[next] 减 1
            如果入度[next] 变成了 0，把 next 入队
  4. 结束。此时如果【结果序列的长度 < 顶点总数】，说明有环

逐步追踪一遍（用第二节那张课表，按编号 0~7 是"高等数学、线性代数、程序设计基础、数据结构、算法分析、操作系统、编译原理、计算机网络"）：

第一步，统计入度：

第二步：入度为 0 的只有顶点 0 → 队列 [0]

第三步，循环：

队列空，输出了 8 个顶点 = 总数，所以无环，算法成功。

代码：

static (List<int> order, List<int> remaining) TopoSortKahn(DiGraph g)
{
    var indeg = new int[g.VertexCount];
    for (int v = 0; v < g.VertexCount; v++)
        foreach (int next in g.Neighbors(v))
            indeg[next]++;                        // 有一条 v -> next，next 就多一个前驱

    var queue = new Queue<int>();
    for (int v = 0; v < g.VertexCount; v++)
        if (indeg[v] == 0) queue.Enqueue(v);

    var order = new List<int>(g.VertexCount);
    while (queue.Count > 0)
    {
        int v = queue.Dequeue();
        order.Add(v);
        foreach (int next in g.Neighbors(v))
            if (--indeg[next] == 0)               // v 做完了，next 少一个前置条件
                queue.Enqueue(next);
    }

    var remaining = new List<int>();
    for (int v = 0; v < g.VertexCount; v++)
        if (indeg[v] > 0) remaining.Add(v);       // 入度没归零 = 还没被排进去

    return (order, remaining);
}

实测：

=== 实验一：Kahn 算法 —— 课程表的修读顺序 ===

  课程依赖（u -> v 表示 u 是 v 的先修课）：

    线性代数         <- 高等数学
    程序设计基础       <- 高等数学
    数据结构         <- 线性代数、程序设计基础
    算法分析         <- 数据结构
    操作系统         <- 程序设计基础
    编译原理         <- 算法分析、操作系统
    计算机网络        <- 操作系统

  Kahn 算法（队列版）输出：
    [0, 1, 2, 3, 5, 4, 7, 6]

  翻译成一个可行的修读顺序：
    第 1 门：高等数学
    第 2 门：线性代数
    第 3 门：程序设计基础
    第 4 门：数据结构
    第 5 门：操作系统
    第 6 门：算法分析
    第 7 门：计算机网络
    第 8 门：编译原理

  未排入的课程数 = 0（为 0 表示没有环）
  合法性验证：True

和手工追踪完全一致 ✓

注意"一个可行的"这个措辞 —— 这里给出的只是众多合法解中的一个（第二节已指出）。下一小节就实测同一张图能排出三种不同顺序。

代码里的 IsValidTopoOrder 是本节自己写的验证器：检查每条边 $u \to v$ 是否都满足"$u$ 的位置 < $v$ 的位置"。后面每种做法的输出都用它验一遍 —— 本节靠它抓到了一个肉眼很难发现的 bug（第四节）。

复杂度

每个顶点恰好进出队列一次，每条边恰好被减一次入度，所以是线性的 —— 这已经是最好的结果，毕竟光把图读一遍就要 $O(V+E)$。空间：入度数组、队列、结果各 $O(V)$ → $O(V)$。

四、DFS 后序：同一个问题的另一种答案

Kahn 从"入度为 0"入手，还有一条完全不同的路：用 DFS。

观察到：在 DAG 里，如果从 $u$ 能走到 $v$，$u$ 就必须排在 $v$ 前面 —— 路径上每一步都是一条边，每条边都要求起点在前。"能走到"本身就定义了顺序。

所以做法是：DFS 到某个顶点时，先递归处理它的所有后继，处理完了再记录自己（这个次序叫后序遍历，9.2 节）。为什么逆后序就是拓扑序？一句话：

一个顶点被记录的时刻，正是"它的所有后继都已经记录完"的时刻 —— 在后序序列里它一定排在所有后继的前面，反转之后就排在所有后继的后面，这正是拓扑序的要求。 ✓

代码：

static (List<int> order, List<int> postOrder) TopoSortDfsRecursive(DiGraph g)
{
    var visited = new bool[g.VertexCount];
    var post = new List<int>(g.VertexCount);

    void Dfs(int v)
    {
        visited[v] = true;
        foreach (int next in g.Neighbors(v))
            if (!visited[next]) Dfs(next);
        post.Add(v);                              // ★ 后序：所有后继都处理完才记录自己
    }

    for (int v = 0; v < g.VertexCount; v++)
        if (!visited[v]) Dfs(v);

    var order = new List<int>(post);
    order.Reverse();                              // ★ 逆后序 = 拓扑序
    return (order, post);
}

注意外层那个循环 —— 和 12.4 节数连通分量时一模一样：图可能分成几块，必须遍历所有顶点，对没访问过的启动新 DFS。

实测（实验二）：

=== 实验二：同一张图，四种不同的合法顺序 ===

  Kahn（队列）：    [0, 1, 2, 3, 5, 4, 7, 6]
  Kahn（栈）：      [0, 2, 5, 7, 1, 3, 4, 6]
  Kahn（最小堆）：  [0, 1, 2, 3, 4, 5, 6, 7]
  DFS 后序取逆：    [0, 2, 5, 7, 1, 3, 4, 6]

  四种做法给出了三种不同的顺序（栈版和 DFS 版撞车了），但都合法：
    Kahn（队列）   合法性 = True
    Kahn（栈）     合法性 = True
    Kahn（最小堆） 合法性 = True
    DFS 后序取逆   合法性 = True

  DFS 的【原始后序】（没反转，是错的）：
    [6, 4, 3, 1, 7, 5, 2, 0]
    直接当拓扑序用，合法性 = False  <- 必须反转！

横着看：四种做法给出三种结果，但验证器说四个都合法。

竖着看：Kahn 的容器换一下结果就完全不同，算法一个字没改 —— 它真正确定的只有一件事：从"当前入度为 0"的集合里挑一个，挑哪个是自由的。容器决定规则： >

容器	挑选规则	得到的顺序
队列	先进先出	一种合法的拓扑序
栈	后进先出	另一种合法的拓扑序（行为和 DFS 接近）
最小堆	编号最小的先出	字典序最小的那个拓扑序

最容易出错的是后两行：DFS 的原始后序 [6, 4, 3, 1, 7, 5, 2, 0] 直接当拓扑序用，验证器判 False —— 0 是所有课的最终先修课，却被排到了最后一位。"后序取逆"里"取逆"不能省：我写这节代码时第一版就忘了 Reverse()，验证器直接报 False —— 幸好有它，否则肉眼很难看出来。

两种方法怎么选？

工程里默认用 Kahn —— 理由见第七节。

五、反预期实测一：那次"一致"是巧合

实验二里有个细节很容易被扫过去：

  Kahn（栈）：      [0, 2, 5, 7, 1, 3, 4, 6]
  DFS 后序取逆：    [0, 2, 5, 7, 1, 3, 4, 6]

完全一样。

我第一反应是"这不奇怪，栈版 Kahn 本质上就是 DFS" —— 但"感觉像"不是证据。 于是我拿 200 张随机的 6 顶点 DAG 统计两者输出相同的比例：

  注意：上面「栈版 Kahn」和「DFS 后序取逆」的结果一模一样。
  这是巧合还是普遍规律？拿 200 张随机的 6 顶点 DAG 实测：

    两者输出相同：166 / 200 张
    两者输出不同： 34 / 200 张

    一张不同的例子（6 个顶点）：
      边：0->5, 0->3, 0->2, 1->2, 1->3, 2->5
      栈版 Kahn：   [4, 1, 0, 2, 5, 3]
      DFS 后序取逆：[4, 1, 0, 2, 3, 5]

  结论：那张课表上的一致是【巧合】。两者都是合法的拓扑序，但顺序不保证相同。

结果是 166 : 34 —— 83% 的一致率高到，如果你只测几张图，很可能会得出"两者等价"的错误结论。

但反例是实实在在的（上面的 6 顶点图）：两个序列在倒数第二位分道扬镳，都合法，但不同。

为什么巧合率这么高？ 因为栈的"后进先出"和 DFS 的"一条路走到底"确实很像。但两者的机制根本不同：

价值不在于结论，而在于过程："两个算法在小例子上结果一样"不能推出"它们等价"。 本节差点把这个当规律写进正文 —— 是 200 张随机图把它拦下来的。

六、反预期实测二：Kahn 剩下来的，不等于环上的

"输出长度 < 顶点数就有环"很容易引出下一个推论："Kahn 剩下的顶点就是环上的顶点。" 这是错的。 实测（实验三）：

=== 实验三：有环时，Kahn 剩下来的顶点是环上的顶点吗？ ===

  图的构成：
        0 ---> 1 <---> 2 ---> 3

    环是 1 <-> 2；顶点 3 【不在环上】，它只是依赖环上的 2。

  Kahn 输出：        [0]
  Kahn 剩下来的：    [1, 2, 3]

  【反预期】Kahn 剩下来的是 {1, 2, 3} —— 但真正的环只有 {1, 2}。
    顶点 3 不在环上，它只是【排在环的下游】，被环挡住了。

  用三色标记精确找出环上的顶点：{1, 2}

环是 $1 \leftrightarrow 2$，顶点 3 不在环上，它只是依赖环上的顶点 2。

Kahn 的过程：入度是 0:0, 1:2, 2:1, 3:1，只有顶点 0 入度为 0；输出它之后顶点 1 的入度从 2 变成 1 —— 然后队列就空了。

为什么 3 也被剩下了？ 因为 Kahn 只能输出"所有前置条件都已满足"的顶点，而顶点 3 的前置条件永远满足不了。但"进不了队列"不等于"在环上" —— 3 是环的下游，是被波及的，不是肇事的。

要精确找环，得用 12.4 节的三色标记，本节加强了一点：维护一条"当前 DFS 路径"，遇到灰色顶点时，路径上从它开始到末尾的那一段就是一个环：

void Dfs(int v)
{
    color[v] = 1;                             // 进入：变灰
    path.Add(v);
    foreach (int next in g.Neighbors(v))
    {
        if (color[next] == 1)
        {
            int start = path.IndexOf(next);   // ★ 绕回路径上了 -> 发现环
            for (int i = start; i < path.Count; i++) onCycle.Add(path[i]);
        }
        else if (color[next] == 0)
        {
            Dfs(next);
        }
    }
    path.RemoveAt(path.Count - 1);
    color[v] = 2;                             // 离开：变黑
}

实测输出 {1, 2} —— 正是环上的两个顶点，把 3 排除掉了。 ✓

两种方法给出的"嫌疑名单"不一样：

报错只给 remaining 是不够用的：用户看到 {1, 2, 3} 会去检查顶点 3 的依赖，结果发现 3 完全没问题。包管理器报"以下 17 个包无法安装"用前者就够；构建工具报"循环依赖：A → B → C → A"必须用后者。

七、工程警告：递归 DFS 在长链上会崩溃

Kahn 和 DFS 都是 $O(V+E)$，那是不是随便用哪个都行？不是。 实测（实验五，链状 DAG）：

=== 实验五：递归 DFS 后序在长链 DAG 上会发生什么 ===

  构造一条链状 DAG：0 -> 1 -> 2 -> ... -> 99,999
  顶点数 = 100,000，边数 = 99,999，它显然是 DAG（编号严格递增）。

  先用 Kahn 算法试（队列 + 循环，不占调用栈）：
    Kahn 完成，顺序长度 = 100,000 ✓

  换成迭代版 DFS（显式栈）：
    迭代 DFS 完成，顺序长度 = 100,000 ✓

  最后用递归版 DFS —— DFS 深度会达到 100,000 层：

然后进程死了（下面这段是从控制台原样复制的）：

Stack overflow.
Repeat 9628 times:
--------------------------------
   at Program.<<Main>$>g__Dfs|0_15(Int32, <>c__DisplayClass0_1 ByRef)
--------------------------------
   at Program.<<Main>$>g__TopoSortDfsRecursive|0_3(DiGraph)
   at Program.<<Main>$>g__RunDeepChainExperiment|0_8()
   at Program.<Main>$(System.String[])

Repeat 9628 times 是运行时自己打出来的 —— 它把同一个递归帧折叠了：实际只压进 9,628 层栈帧，栈就满了，远不是 10 万层。最后四行才是真正的调用链：Main → RunDeepChainExperiment → TopoSortDfsRecursive → Dfs。

进程直接终止，退出码 253（即 0xC00000FD 的低 8 位；用 Start-Process 拿到的是十进制 -1073741571）。

9,628 这个数字值得和 2.2 节对一下：那里一个只有几个局部变量的递归函数能压 16,074 层，这里少了约 40% —— 因为本节 Dfs 里有一个 foreach（编译器为它生成了迭代器状态）、一个闭包引用和一个 List 参数，栈帧更胖。

能递归多深取决于栈帧大小，不是语言规定的层数 —— 而且这个数字每次运行还会小幅波动（我三次分别是 9635、9630、9628）。

这里要记住的三件事：

所以要写成迭代版（本节代码里的 TopoSortDfsIterative）：

while (stack.Count > 0)
{
    var (v, idx) = stack.Pop();
    var neighbors = g.Neighbors(v);

    if (idx < neighbors.Count)
    {
        stack.Push((v, idx + 1));         // 回来时从下一个邻居继续
        int next = neighbors[idx];
        if (!visited[next])
        {
            visited[next] = true;
            stack.Push((next, 0));
        }
    }
    else
    {
        postOrder.Add(v);                 // 邻居全处理完了，记录自己
    }
}

关键技巧：栈里存的不是 v，而是 (v, 下一个待处理邻居的下标) —— "递归到一半"的状态被显式保存在了堆上。

一句话结论：要拓扑排序，工程里默认用 Kahn —— 没有递归深度风险、能直接检测环、换最小堆还能得字典序最小解。但"用 DFS 求逆后序"这个方法本身也要理解：面试会问，它也是后面强连通分量等算法的基础。

性能实测：哪个结论可靠，哪个不可靠

三者复杂度不同，实测差多少？（10 万顶点、299,999 条边，各跑 10 次取最快）

  随机 DAG：顶点 100,000，边 299,999（编号小的指向编号大的，所以一定是 DAG）

  Kahn（队列）    ：    4.7 ms   （10 次取最快）
  DFS 后序（迭代）：    3.7 ms   （10 次取最快）
  Kahn（最小堆）  ：    8.7 ms   （10 次取最快）

  最小堆 / 队列 =  1.88 倍   <- log n 的代价，稳定可复现
  DFS    / 队列 =  0.80 倍   <- 同量级，见下面的噪声实测

  这两个 O(V+E) 的实现到底谁快？各单独跑 8 轮，原样列出：
    Kahn（队列）：4.8  4.9  5.3  6.0  5.6  4.8  6.4  5.0
    DFS 后序    ：4.0  4.0  4.3  4.0  3.9  5.1  3.8  3.7
    Kahn 区间 [4.8, 6.4] ms，DFS 区间 [3.7, 5.1] ms  —— 两者【互相重叠】

  大图上三者都是合法拓扑序：Kahn = True，DFS = True，最小堆 = True
  Kahn 与 DFS 输出是否相同：False

这张表要分两半看 —— 两半的可靠程度完全不同。

上半部分是可信的结论：最小堆版稳定慢约 1.9 倍。因为它把 $O(V+E)$ 升到了 $O((V+E)\log V)$ —— 多出来的 $\log V$ 是真实的算力开销，换个时间跑还是这个量级。想要字典序最小，就得付这笔钱。

下半部分是本节第三个反预期：Kahn 和迭代 DFS 都是 $O(V+E)$，实测根本分不出谁快 —— 8 轮里 Kahn 在 [4.8, 6.4] 之间跳，DFS 在 [3.7, 5.1] 之间跳，两个区间是重叠的。

如果只看"10 次取最快"那一行，会得出"DFS 快 20%"的结论 —— 但那是这一台机器、这一次运行的运气。

我在不同时间点重跑了 5 轮，这个比值在 0.55 ~ 1.08 之间来回摆 —— 同一个算法有时快有时慢，谁赢很大程度上取决于这一轮 GC 什么时候来。

这一课比"谁快"本身重要：

1.1 节讲过"大 O 相同 ≠ 实际一样快"（那里前缀和比暴力快 170 倍，是实打实的差距）。但反过来同样要小心："实测 A 比 B 快一点"，在同量级下不构成结论。

一个可操作的判据：差距不到 2 倍、且复现不了五次以上的"谁更快"，不要写进结论。

选型结论（和那 1 毫秒无关）：

八、练习

练习 13.1.1（手算 Kahn） 对于下面的图（边 $u \to v$ 表示 $u$ 必须先于 $v$）：

  0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3, 3 -> 4, 2 -> 5, 5 -> 4

(a) 写出每个顶点的入度。 (b) 用 Kahn 算法（队列版）逐步追踪，写出每步的队列和输出。 (c) 这个图有环吗？你怎么判断？

练习 13.1.2（判断） 判断对错并说明理由： (a) 任何有向图都至少有一个拓扑序。 (b) 一个 DAG 的拓扑序是唯一的。 (c) Kahn 结束时还有顶点没被输出，说明图里有环。 (d) 把队列换成栈，输出的就不再是合法拓扑序了。

练习 13.1.3（工程判断） 构建系统要根据文件依赖决定编译顺序：a.c 包含 a.h；b.c 包含 a.h、b.h；main.c 包含 b.h。 (a) 怎么建图？边从谁指向谁？ (b) 一个合法的编译顺序是什么？ (c) 如果 a.h 改成包含 b.h，b.h 又包含 a.h，会发生什么？构建系统该怎么报错？

练习 13.1.4（字典序最小） 输出字典序最小的拓扑序（每个位置都尽量小）。 (a) 说出做法，并解释为什么这样改就够了。 (b) 为什么不能"先随便求一个再调小"？

练习 13.1.5（挑战·判断拓扑序是否唯一） (a) 怎么判断一个 DAG 的拓扑序是否唯一？说出判据和理由。 (b) 用练习 13.1.1 的图验证你的判据。 (c) 在 Kahn 算法里要加什么代码？给出关键片段。

九、练习答案

13.1.1

(a) 入度表：

(b) 逐步追踪：

拓扑序：[0, 1, 2, 3, 5, 4]

验证：4 的两个前置条件 3、5 都排在它前面（第 4、5 位 < 第 6 位）✓

注意第 4、5 轮：顶点 4 入度为 2，只有 3 和 5 都被输出后才会归零 —— 3 出队时它只从 2 变成 1，还不能进队列。这是新手最容易漏的一步。

(c) 没有环 —— 输出长度 6 = 顶点总数 ✓

13.1.2

两条补充：(c) 剩下 ≠ 在环上（第六节实测）。(d) 的实测：队列版 / 栈版 / 最小堆版都合法。

13.1.3

(a) 顶点是每个文件；边是"被包含的文件 → 包含它的文件"（a.h、b.h、main.c、a.c、b.c）。

  a.h ──> a.c
   │
   ├───> b.c
   │      ↑
  b.h ─────┘
   │
   └───> main.c

方向依据："先做" → "后做"。画反了（b.c → a.h），Kahn 会告诉你"先编译 main.c" —— 而那时 a.h 还不存在。

(b) 编译顺序（一个合法解）：

  a.h → b.h → main.c → a.c → b.c

逐条验证：a.h→a.c（1<4）✓、a.h→b.c（1<5）✓、b.h→b.c（2<5）✓、b.h→main.c（2<3）✓ —— 全部满足。（a.c 和 main.c 可互换，拓扑序不唯一）

(c) 互相包含会形成环 a.h → b.h → a.h。 Kahn 跑起来：两个顶点的入度都是 1，队列一开始就是空的 —— 结果长度 0 < 2，判定有环，必须报错停下。

构建系统该怎么报错：

13.1.4

(a) 做法：把 Kahn 算法里的队列换成最小堆，用顶点编号当优先级。

var heap = new PriorityQueue<int, int>();
for (int v = 0; v < g.VertexCount; v++)
    if (indeg[v] == 0) heap.Enqueue(v, v);        // 优先级 = 编号

要证两件事：(1) 仍是合法拓扑序 —— 换容器不改变 Kahn 的正确性论证（见 13.1.2(d)）。(2) 是字典序最小的 —— 设首元素是 $x$，$x$ 是所有入度为 0 的顶点中编号最小的，而任何合法拓扑序的首元素必须是某个入度为 0 的顶点，所以它 $\ge x$；若 $> x$ 则已输，若 $= x$ 则归约到同一问题 —— 归纳成立 ✓（实测给出 [0,1,2,3,4,5,6,7]）

(b) 因为局部调整会破坏合法性。 设某个合法拓扑序是 [3, 1, 2]，你想把首元素 3 调成 1 —— 但如果图里有边 $1 \to 3$，"1 在 3 前面"就是非法的。更麻烦的是，往前挪一个元素会挤动它后面所有元素，你不知道会不会连带违反别的边。

本质原因：合法拓扑序的集合是一个偏序的线性扩展（linear extension），元素关系是部分确定的、不是全序，"排好序再微调"刻画不了它。必须边构造边决策 —— 这正是贪心（第 14 章）。

13.1.5

(a) 判据：Kahn 的任何时刻，只要【候选集合大小曾经超过 1】就不唯一；反之（从头到尾都恰好是 1）则唯一。

为什么？ 候选集合就是可以自由选择先做哪个的顶点。$\ge 2$ 个 → 选任意一个都合法 → 至少两条输出路径，不唯一；恰好 1 个 → 没得选，唯一。注意是"任何时刻"：出现过一次就已不唯一。

(b) 用练习 13.1.1 的图验证：

所以不唯一 ✓ —— [0,1,2,3,5,4] 和 [0,2,1,3,5,4]（先做 2 再做 1）都合法。

(c) 代码片段：

bool unique = true;
while (queue.Count > 0)
{
    if (queue.Count > 1) unique = false;          // ★ 只有这一行是新增的

    int v = queue.Dequeue();
    order.Add(v);
    foreach (int next in g.Neighbors(v))
        if (--indeg[next] == 0) queue.Enqueue(next);
}

容易写错的版本：写在 Dequeue 之后判断 —— 那样算的是"出队后"的大小，会漏掉"初始时就有多个入度为 0 的顶点"的情况。判据必须在出队前检查。

十、常见错误

十一、本节总结

1. 拓扑排序：把 DAG 排成线性序列，使每条边都从前往后指。存在拓扑序 ⟺ 图无环。
2. 约定：边 $u \to v$ 表示 $u$ 先做、$v$ 后做。画反了结果就全反。
3. Kahn 算法：统计入度 → 入度为 0 的入队 → 反复出队、把邻居入度减 1、减到 0 就入队。$O(V+E)$。
4. DFS 后序：递归处理完所有后继再记录自己，最后反转序列（忘反转实测非法）。$O(V+E)$。
5. 拓扑序不唯一：同一张图四个版本给出三种合法顺序，验证器全判 True。换最小堆即得字典序最小解。
6. 反预期一：栈版 Kahn 和 DFS 后序在课表上结果一致是巧合 —— 200 张随机小图实测 166 : 34。
7. 反预期二：Kahn 剩下的顶点 ≠ 环上的顶点。剩下的 {1,2,3} 里 3 只是环的下游 —— 精确报环要用 12.4 节的三色标记。
8. 工程结论：默认用 Kahn。10 万顶点链状 DAG 上递归 DFS 栈溢出崩溃（退出码 253，实际只压进 9,628 层栈帧），Kahn 和迭代 DFS 都正常 —— 选型关键是栈溢出风险，不是那几毫秒。
9. 反预期三：同量级的两个实现在微基准上分不出胜负。Kahn（队列）与迭代 DFS 各跑 8 轮，区间互相重叠、比值在 0.55 ~ 1.08 间摆动；而最小堆版慢 1.88 倍是稳定可复现的 —— 差距不到 2 倍、复现不了五次以上的"谁更快"，不要当成结论。

下一节衔接：本节处理的图都不带权 —— 边只表示"谁先谁后"，没有"多贵"。但现实中的图几乎都带权重：城市之间的距离、链路的延迟、任务的耗时。

12.3 节说过 BFS 一定能找到最短路径，但那有一个未明说的前提："每条边长度相同"。 一旦边长不等 BFS 就失效了 —— 下一节先把这个边界说清楚，再引出 13.3 节的 Dijkstra。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "13.1",
  "title": "拓扑排序与依赖解析",
  "covered": [
    "DAG 与依赖关系的建模（边的方向约定）",
    "拓扑序的形式化定义与「不唯一」性质",
    "「存在拓扑序 ⟺ 无环」的证明思路",
    "入度的定义与 Kahn 算法的逐步追踪（8 顶点课表）",
    "Kahn 算法的 C# 实现与实测（[0,1,2,3,5,4,7,6]）",
    "拓扑序合法性验证器的实现与用途",
    "DFS 后序取逆解法与「为什么必须反转」的论证",
    "四种实现的对比实测（队列/栈/最小堆/DFS）",
    "反预期实测一：栈版 Kahn 与 DFS 后序的一致是巧合（200 张随机图 166:34）",
    "反预期实测二：Kahn 的 remaining ≠ 环上顶点（三色标记精确找环）",
    "字典序最小拓扑序的最小堆做法与正确性论证",
    "10 万顶点 DAG 上 Kahn vs 迭代 DFS 的性能实测",
    "递归 DFS 在 10 万顶点长链上栈溢出的实测与工程结论"
  ],
  "unresolved": [
    "带权图的最短路径留到 13.2 / 13.3",
    "强连通分量（Tarjan / Kosaraju）超出本书范围",
    "拓扑序唯一性判据的完整证明只给了直觉论证",
    "最小生成树超出本书范围"
  ],
  "canonical_terms": {
    "拓扑排序（Topological Sort）": "把有向无环图排成线性序列，使每条边的起点都排在终点之前",
    "入度（In-Degree）": "指向该顶点的边数，即该顶点的前置依赖个数",
    "有向无环图（DAG）": "不含环的有向图，存在拓扑序的充要条件",
    "字典序最小拓扑序": "用最小堆代替队列，每次挑编号最小的可选顶点"
  },
  "symbols_units": {
    "V": "顶点数",
    "E": "边数",
    "indeg(v)": "顶点 v 的入度",
    "pos[v]": "顶点 v 在输出序列中的下标（用于合法性验证）"
  },
  "assumptions": [
    "读者已掌握 12.2 的 DFS 与 12.4 的三色标记",
    "读者理解 5.2 的队列",
    "边的方向约定为「起点先做、终点后做」"
  ],
  "word_count_actual": 4520,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑（AMD Ryzen 7 9700X），输出见正文",
    "项目文件：99-tools/samples/Ch13/Sec131/",
    "Kahn 输出 [0,1,2,3,5,4,7,6]、四种做法均通过合法性验证、原始后序验证 False 均为实测",
    "200 张随机 6 顶点 DAG 上栈版 Kahn 与 DFS 后序的异同（166:34）为实测",
    "实验三的 remaining={1,2,3} 与三色标记 {1,2} 均为实测",
    "10 万顶点性能实测：三者同轮对比取 10 次最快，另附 8 轮原始计时以展示噪声区间",
    "最小堆版实测 1.88 倍（多次运行 1.7~1.9 倍），与 log V 因子的量级相符",
    "栈溢出实验用 --deep 开关单独运行，退出码 0xC00000FD（十进制 -1073741571），栈帧 9,628 层为实测",
    "术语写法与 glossary.md 一致（拓扑排序、入度、三色标记、环检测）"
  ],
  "known_issues": [
    "正文初稿误写「四种顺序各不相同」——实测只有三种（栈版 Kahn 与 DFS 后序输出一致），已按实测修正",
    "原本准备把「栈版 Kahn 等价于 DFS 后序」当规律写入，200 张随机图实测 166:34 有反例，改为「巧合」并附反例",
    "C# 顶级语句中局部函数不能捕获 out 参数（CS1628），TopoSortDfsRecursive 改为返回元组",
    "首版计时只跑 5 次取最快，同一份代码在不同轮次给出 0.55~1.08 的比值 —— 改为一并给出「10 次取最快」与「8 轮原始计时」，并新增反预期三：同量级的微基准测不出稳定差异",
    "栈溢出段初稿输出是手工简化的（写了「重复约 2 万行」和一个并不存在的 List.GetEnumerator 帧），已按控制台原样重写为 Repeat 9628 times",
    "实测递归深度 9,628 层，比 2.2 节的 16,074 层少约 40% —— 因本节 Dfs 的栈帧更胖（foreach 迭代器 + 闭包引用），正文补充了这一对比"
  ],
  "next": "13.2 无权最短路：BFS 的正确用法"
}