第 93 章　拓扑排序¶

本章配套 1 道例题，见 §例题。

前置：图的表示与遍历、队列与双端队列、优先队列与堆

拓扑排序回答一个判定问题——有向图有没有环——顺带产出一个可用的执行顺序：每条边 \(u \to v\) 都满足 \(u\) 排在 \(v\) 前面。算法就是一遍 BFS（Kahn），十来行。

它真正的价值在下游：拓扑序就是 DAG 上 DP 的合法转移顺序，无后效性从这里来。 DAG 上的最短路因此允许负权，\(O(n+m)\) 一遍递推就够。

1　DAG 与拓扑序¶

DAG（Directed Acyclic Graph）：没有环的有向图。

拓扑序：把所有点排成一个线性序列，使得每条边 \(u \to v\) 都满足 \(u\) 排在 \(v\) 前面。

基本定理：

\[\text{有向图存在拓扑序} \iff \text{它是 DAG}\]

「⟸」的构造性证明就是 Kahn 算法本身：DAG 里必定存在入度为 0 的点（否则从任意点一直往前走必然重复访问某点，形成环），取出它、删掉它的出边，剩下的图仍是 DAG，归纳即可。「⟹」显然：环上的点谁都不能排在最前。

关于拓扑序的四个事实	说明
拓扑序一般不唯一	入度为 0 的点有多个时，先取哪个都行
拓扑序唯一 ⟺ 每一步都只有一个入度 0 点	等价于图上存在一条经过所有点的路径（哈密顿路）
拓扑序的逆序是反图的拓扑序	求「以某点为终点的最长路」时常用
拓扑序个数	计数是 #P-完全问题；\(n \le 20\) 时用状压 DP（状压 DP）

用途：

场景	怎么用
判有向图是否有环	拓扑排序能否排完全部 \(n\) 个点
课程 / 任务的先后依赖	拓扑序就是可行的执行顺序
DAG 上 DP	按拓扑序递推，天然满足无后效性（93.4）
关键路径（AOE 网）	拓扑序上正推最早开始、逆推最晚开始（图论进阶：k 短路与关键路径）
强连通分量缩点后的处理	缩点后必是 DAG（强连通分量）
判断差分约束是否有解	转化成负环检测（最短路）

2　Kahn 算法（入度法）¶

三步：

统计所有点的入度，把入度为 0 的点全部入队；
每次取出一个点 \(u\) 加入答案，把它所有出边 \(u \to v\) 的 \(v\) 的入度减 1，减到 0 就入队；
队列空时结束。若答案里的点数 \(< n\)，说明有环（环上的点入度永远减不到 0）。

拓扑排序的经典模板（例题「旅行计划」）就是这个：

for(int i=1;i<=n;++i) if(!rd[i]) q.push(i);        // rd 是入度
while(!q.empty()){
    top[++cnt]=q.front();q.pop();
    for(int i=head[top[cnt]];i;i=bot[i].nx){
        rd[bot[i].nd]--;
        if(!rd[bot[i].nd]) q.push(bot[i].nd);
    }
}

模板¶

def topo_sort(n, start, adj, indeg):
    """Kahn 入度法拓扑排序（CSR 存图，点编号 1..n）。O(n + m)。

    返回 (order, is_dag)：order 是一个合法拓扑序；
    is_dag 为 False 说明图里有环（此时 order 是「环外部分」的拓扑序）。

    ★ 用列表当队列：order 既是结果也是队列，`for u in order` 一边遍历一边
      append。BFS / Kahn 从不真的删元素，所以这样是安全的，
      而且省掉了 deque.popleft() 的方法调用——n = 3e5 时能省掉 3e5 次调用。
    """
    deg = indeg[:]                           # 复制，不破坏调用方的入度数组
                                             # deg[v] 会被减到 0，是「还欠几个前驱」
    order = [v for v in range(1, n + 1) if deg[v] == 0]   # 无前驱的点先入队
    for u in order:                          # 列表在迭代中扩展是安全的
        # u 已确定排在最终序列里，于是它对每个后继的「约束」就此解除
        for i in range(start[u], start[u + 1]):
            v = adj[i]
            d = deg[v] - 1                   # 抵消掉 u -> v 这一条前驱约束
            deg[v] = d
            if d == 0:                       # 前驱全部就位 -> 可以出场了
                order.append(v)              # 归零的时刻就是入队的时刻，早一步都不行
    # 环上的点入度永远减不到 0，所以排不进 order；点数不足即说明有环
    return order, len(order) == n

for u in order: 这个写法是 Python 图论的一个小红利。它成立的前提是「队列只在尾部追加、指针只往前走」——BFS、Kahn、树上求 BFS 序都满足。但 0-1 BFS、SPFA 需要 appendleft 或重复入队，就必须用 deque（见队列与双端队列、最短路）。

判环：三种写法的对比¶

判环方式	复杂度	Python 评价
Kahn：排出的点数 \(< n\)	\(O(n+m)\)	✅ 首选，顺手得到拓扑序
DFS 三色标记（白/灰/黑），遇到灰点即有环	\(O(n+m)\)	⚠️ 必须写迭代 DFS，代码长
并查集	—	❌ 不能用：并查集判的是无向图的环

⚠️ 有向图的环不能用并查集判。并查集只知道「连通」，不知道方向。\(1\to2\)、\(1\to3\) 在并查集里和 \(1\to2\)、\(2\to1\) 长得一样。判有向环只有拓扑排序和 DFS 两条路。

自环与重边¶

情况	对 Kahn 的影响
自环 \(u \to u\)	\(u\) 的入度永远 \(\ge 1\)，自动被判为「有环」✅ 不用特判
重边 \(u \to v\) 两次	\(v\) 的入度加了 2，出边也遍历两次，减回 0 ✅ 自洽
孤立点（入度出度都 0）	一开始就入队 ✅

3　字典序最小的拓扑序¶

题目常问「若有多个拓扑序，输出字典序最小的那个」。

做法只有一处改动：把队列换成小根堆。 每一步在「当前所有入度为 0 的点」里取编号最小的。

from heapq import heapify, heappush, heappop


def topo_sort_lexmin(n, start, adj, indeg):
    """字典序最小的拓扑序。O((n + m) log n)。

    与 topo_sort 唯一的区别：队列 -> 小根堆。
    """
    deg = indeg[:]                           # deg[v] = v 还欠几个前驱
    h = [v for v in range(1, n + 1) if deg[v] == 0]
    heapify(h)                               # ★ O(n) 建堆，比逐个 heappush 快
    order = []                               # 结果和候选池必须分开：候选池要能重排
    ap = order.append                        # 绑定方法，省掉 n 次属性查找
    while h:
        u = heappop(h)                       # 在「当前所有可选点」里取编号最小的
        ap(u)
        for i in range(start[u], start[u + 1]):
            v = adj[i]
            d = deg[v] - 1
            deg[v] = d
            if d == 0:
                heappush(h, v)               # 新解锁的点丢进候选池，等下一轮竞争
    return order, len(order) == n            # 点数不足 = 有环

⚠️ 两个常见错法： 1. 先跑普通拓扑排序，再把结果排序 —— 排完就不是拓扑序了； 2. 把每个点的邻居表排序，然后用普通队列 —— 队列是 FIFO，先入队的点可能编号更大，取出顺序仍然不是字典序最小。

贪心必须发生在「取出」的时刻，所以必须换成堆。

三种拓扑排序方式的对比¶

方式	复杂度	得到的序	Python 评价
Kahn + 列表/`deque`	\(O(n+m)\)	任意一个	✅ 默认；\(n=3\times10^5\) 轻松
Kahn + 小根堆	\(O((n+m)\log n)\)	字典序最小	✅ \(n \le 2\times10^5\) 可行
DFS 逆后序（退出时压栈，最后反转）	\(O(n+m)\)	任意一个	⚠️ 不用算入度，但 Python 必须写迭代 DFS

变体：

要求	做法
字典序最大	入堆时存 `-v`，取出时取负；或用最大堆技巧（优先队列与堆）
「让编号大的点尽量靠前」	⚠️ 不等于字典序最大！正解是在反图上求字典序最小，再整体反转
要求某些点必须相邻	一般无法用拓扑排序直接做，需要额外建图或状压

⚠️ 「编号大的尽量靠前」是个经典陷阱。字典序最大是「第一位尽量大，其次第二位尽量大……」，而「大的尽量靠前」是「\(n\) 的位置尽量靠前，然后 \(n-1\) 尽量靠前……」，两者不同。后者要在反图上贪心「小的尽量靠后」，即反图求字典序最小后反转。

4　DAG 上的 DP¶

DAG 上 DP 之所以简单，是因为拓扑序直接给出了「无后效性」的执行顺序。

按拓扑序遍历，处理 \(u\) 时它的所有前驱都已算完，于是可以直接往后继推—— 这就是「无后效性」，也是 DP 能成立的全部前提。它带来的一个直接结果是：DAG 上的最短路允许负权，\(O(n+m)\) 一遍递推就够，既不用 Dijkstra（要求非负权）也不用 Bellman-Ford（\(O(nm)\)）。见最短路。

具体能算什么——最长路、路径计数、关键路径、食物链计数——以及它们的模板，在 DAG 上的 DP。本章只负责「为什么能这么算」。

5　例题¶

题号	题名	难度	题解
LC207	课程表	中等	题解

LC207 课程表¶

LC 207. 课程表给出课程总数与若干「先修 → 后修」的依赖对，问能否修完全部课程。 题面问的是「能不能」，本质就是一次有向图判环—— Kahn 算法排出的点数是否等于 \(n\)，就是答案。

三处值得落实到代码上：

依赖对给的形式是 [后修, 先修]，建边方向要写成「先修 → 后修」。方向反了之后入度统计整个对称过来，对称的图仍然能过，链状的图才会露馅。
课程数上限 \(2000\)、依赖数上限 \(5000\)，\(O(n + m)\) 的 Kahn 一遍就够，不必去凑字典序最小那一版的堆。
只判环时可以不保留拓扑序，累计出队个数即可；若题面改成「输出一个可行的修课顺序」，就是同一份代码多一个 append。

自环（某门课把自己列为先修）会让该点入度永远不为 \(0\)，被自动判成有环，不需要特判；重复给出的同一条依赖会让入度加两次、出边也遍历两次，同样自洽。

6　本章速查¶

拓扑排序¶

要点	结论
拓扑序定义	每条边 \(u\to v\) 都满足 \(u\) 排在 \(v\) 前
存在性	存在拓扑序 ⟺ 是 DAG
唯一性	每一步只有一个入度 0 点 ⟺ 存在哈密顿路
Kahn 三步	入度 0 入队 → 取出并把后继入度 \(-1\) → 减到 0 入队
判环	排出的点数 \(< n\)
❌ 并查集判有向环	不行，它不知道方向
自环	入度永远 \(\ge1\)，自动被判有环，不用特判
重边	入度加 2、出边遍历 2 次，自洽
队列容器	列表当队列 + `for u in order`（Kahn 只在尾部追加）
什么时候必须 `deque`	0-1 BFS、SPFA（需要 `appendleft` / 重复入队）
字典序最小拓扑序	队列换小根堆，\(O((n+m)\log n)\)
❌ 先拓扑再排序	排完就不是拓扑序了
❌ 邻居表排序 + 普通队列	队列是 FIFO，取出顺序仍不对
「编号大的尽量靠前」	⚠️ 不是字典序最大；反图求字典序最小再反转
DAG 上 DP	按拓扑序递推，天然无后效性
DAG 最短路	允许负权，\(O(n+m)\)，不用 Dijkstra
关键路径	拓扑序正推 `ve` + 逆推 `vl`（图论进阶：k 短路与关键路径）

第 93 章 拓扑排序¶

1 DAG 与拓扑序¶

2 Kahn 算法（入度法）¶

模板¶