图的拓扑排序 (Topological Sorting) 复习指南

1. 核心概念

1.1 定义

拓扑排序是对有向无环图 (DAG, Directed Acyclic Graph) 的顶点的一种排序。
它使得对于图中的每一条有向边 $(u, v)$，顶点 $u$ 在排序中都出现在顶点 $v$ 之前。

1.2 适用范围 (AOV 网)

  • AOV 网 (Activity On Vertex Network)：用顶点表示活动，用边表示活动间的优先关系。
  • 前提条件：图必须是 有向 的，且 没有环 (Acyclic)。
  • 性质：
    1. 如果存在环，则无法进行拓扑排序。
    2. 一个 DAG 的拓扑排序序列可能不唯一。

2. 核心算法实现

最常用的算法是基于 入度 (Indegree) 的算法（也称为 Kahn 算法）。

2.1 算法步骤 (Kahn 算法)

  1. 初始化：计算图中所有节点的入度。
  2. 入队：将所有入度为 0 的节点放入队列（Queue）中。
  3. 循环处理：
    • 当队列不为空时，取出队首节点 $u$，放入结果序列。
    • 遍历 $u$ 的所有邻接点 $v$ (即存在边 $u \to v$)。
    • 将 $v$ 的入度减 1。
    • 如果 $v$ 的入度变为 0，则将 $v$ 入队。
  4. 判断结果：如果结果序列中的节点数等于图的总节点数，则排序成功；否则说明图中有环。

2.2 复杂度

  • 时间复杂度：$O(V + E)$，其中 $V$ 是顶点数，$E$ 是边数。需要遍历所有点和所有边。
  • 空间复杂度：$O(V)$，需要存储入度数组和队列。

2.3 另一种思路 (DFS)

  • 利用深度优先搜索。
  • 当一个节点的所有后继节点都访问完毕后，将该节点压入栈中。
  • 最后栈中元素的出栈顺序即为拓扑排序序列。
  • 注意：DFS 方法在检测环时不如入度法直观，考试中推荐优先掌握入度法。

3. 常见题型与考法

题型一：判断拓扑序列的合法性 (手算题)

描述：给出一个有向图，问下列哪个序列是合法的拓扑排序？
解题技巧：

  1. 首元素检查：选项中的第一个元素，在原图中必须是入度为 0 的点。
  2. 模拟删除：按选项顺序，依次在脑海中“删除”该点及其发出的边，检查下一个点是否变成了入度为 0。
  3. 逆序检查：如果选项中出现 $B$ 在 $A$ 前面，但在图中存在路径 $A \to \dots \to B$，则该选项错误。

题型二：判环 / 死锁检测

描述：判断一个依赖关系是否存在循环依赖，或者判断课程表能否修完。
核心逻辑：

  • 运行拓扑排序算法。
  • 若最终输出的节点数 < 总节点数 $V$，说明存在环。
  • 注意：在操作系统中，这常用于死锁检测（资源分配图）。

题型三：求字典序最小/最大的拓扑序列

描述：如果存在多个合法的拓扑序列，要求输出字典序最小的那一个。
考法变化：

  • 普通队列 vs 优先队列：标准的 Kahn 算法使用 FIFO 队列。若要求字典序最小，需将队列 (Queue) 换成 最小堆 (Priority Queue / std::priority_queue in C++)。
  • 注意：每次从入度为 0 的集合中取节点时，必须取当前编号最小的那个。

题型四：判断拓扑序列的唯一性

描述：判断该图是否只有一个唯一的拓扑排序序列。
判定标准：

  • 在 Kahn 算法的每一步过程中，队列中的元素个数必须始终为 1。
  • 如果有某一时刻队列中元素个数 $>1$，说明此刻有多个入度为 0 的点可以选择，因此排序不唯一。
  • 补充：这也意味着图中存在一条贯穿所有节点的哈密顿路径 (Hamiltonian Path)。

题型五：求关键路径 / 最长路径 (AOE 网前置)

描述：在一个 DAG 中，求耗时最长的路径。
关联：虽然这是 AOE 网的内容，但通常需要按照拓扑序进行动态规划 (DP)。

  • 状态转移：$dist[v] = \max(dist[v], dist[u] + weight(u, v))$，其中 $u$ 是 $v$ 的前驱。

4. 易错点与注意事项

⚠️ 1. 区分 AOV 和 AOE

  • AOV (Activity On Vertex)：顶点是活动，边是顺序。$\to$ 拓扑排序解决顺序问题。
  • AOE (Activity On Edge)：边是活动(带权)，顶点是事件。$\to$ 关键路径解决工期问题。
  • 不要混淆两者的定义。

⚠️ 2. 离散图的处理

  • 图可能是非连通的（例如两个独立的子图）。
  • 注意：拓扑排序算法可以处理非连通图。只要没有环，所有节点最终都会进入序列。不要以为图不连通就不能拓扑排序。

⚠️ 3. 数据结构的选择 (代码题)

  • 邻接表：最常用，适合稀疏图，方便遍历 $u$ 的邻居。
  • 邻接矩阵：适合稠密图，但在遍历邻居时需要 $O(V)$ 时间，总时间复杂度会退化到 $O(V^2)$。做题首选邻接表。

⚠️ 4. 0 入度节点的遗漏

  • 初始化陷阱：在算法开始前，务必遍历一次所有节点，把初始入度为 0 的节点全部入队。不要只把第一个找到的入队。

⚠️ 5. 环的输出

  • 有些题目要求：如果有环，输出环中的节点。
  • 标准的拓扑排序只能告诉你“有环”，但留在图中的节点（入度始终无法减为 0 的节点）就是构成环以及环下游的节点，不一定是纯粹的简单环。若需精确找环，需用 DFS (三色标记法)。

5. 代码模板 (C++ STL)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 返回是否可以完成拓扑排序，如果可以，result 存储排序结果
bool topologicalSort(int numCourses, vector<vector<int>>& adj, vector<int>& result) {
    vector<int> indegree(numCourses, 0);
    
    // 1. 计算入度
    for (int i = 0; i < numCourses; i++) {
        for (int neighbor : adj[i]) {
            indegree[neighbor]++;
        }
    }
    
    // 2. 将入度为 0 的节点入队
    // 如果要求字典序最小，将 queue 换成 priority_queue<int, vector<int>, greater<int>>
    queue<int> q; 
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }
    
    // 3. BFS 处理
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        result.push_back(u);
        
        for (int v : adj[u]) {
            indegree[v]--;
            if (indegree[v] == 0) {
                q.push(v);
            }
        }
    }
    
    // 4. 判断是否有环
    return result.size() == numCourses;

}