GESP 8级 · 拓扑排序

📖概念讲解

拓扑排序（Topological Sort）是对有向无环图（DAG）中所有顶点进行线性排序，使得对于每条有向边 (u→v)，u 在排序中总出现在 v 之前。

简单说：给你一堆有先后依赖关系的任务，排出一个合法的执行顺序。典型应用——课表安排、编译依赖、任务调度。

BFS 做法（Kahn 算法）：维护每个节点的入度（被几条边指向）。把所有入度为 0 的点入队，每次取出一个点，把它指向的邻居入度减 1，减到 0 就入队。最后如果输出的节点数 ≠ 总节点数，说明有环。

💡 易错点：拓扑排序的结果不唯一！有多个入度为 0 的点时，取不同顺序都是合法的。题目要求"字典序最小"时要用优先队列（小根堆）代替普通队列。

💻代码示例

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main() {
    int n = 6, m = 6;         // 6个节点，6条边
    vector<vector<int>> adj(n); // 邻接表存图
    vector<int> indeg(n, 0);   // indeg[i] = 节点i的入度
    // 建图：读入 m 条边 u→v
    for(int i=0; i<m; i++) {
        int u, v; cin >> u >> v;  // u 是 v 的前驱
        adj[u].push_back(v);       // u 指向 v
        indeg[v]++;                // v 的入度 +1
    }
    queue<int> q;
    for(int i=0; i<n; i++)
        if(indeg[i] == 0) q.push(i); // 入度为0的点先入队
    vector<int> order;            // 存拓扑序结果
    while(!q.empty()) {
        int u = q.front(); q.pop(); // 取出当前无依赖的点
        order.push_back(u);
        for(int v : adj[u]) {   // 遍历 u 的所有邻居
            indeg[v]--;          // u 被"处理"了，v 的依赖少一个
            if(indeg[v] == 0) q.push(v); // 入度变0，可以排了
        }
    }
    if((int)order.size() != n)
        cout << "有环！无拓扑序" << endl; // 有环说明依赖矛盾
    else {
        for(int x : order) cout << x << " ";
        cout << endl;
    }
    // 输入: 0→1, 0→2, 1→3, 2→3, 2→4, 4→5
    // 输出: 0 1 2 3 4 5
}

🧩互动小测

Q1：拓扑排序只能用于哪种图？

Q2：如果拓扑排序输出的节点数少于总节点数，说明什么？

Q3：要求拓扑序"字典序最小"，应该用什么代替普通队列？

🏋️动手练一练

📝 编程练习

题目：课程表
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1。某些课程有先修要求，比如 [1, 0] 表示想学课程 1 必须先学课程 0。

给定先修关系数组 prerequisites，判断是否可能完成所有课程。如果可以，返回任意一个合法的学习顺序。

输入格式：第一行 numCourses 和 prerequisites 数组，每组 [a, b] 表示学 a 要先学 b。
输出：一个合法的拓扑序列（如不可能输出 -1）。
提示：这就是经典的拓扑排序应用题，核心就是 BFS Kahn 算法。

参考答案：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n);
    vector<int> indeg(n, 0);
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        adj[b].push_back(a);  // 先学 b 再学 a
        indeg[a]++;
    }
    queue<int> q;
    for (int i = 0; i < n; i++)
        if (indeg[i] == 0) q.push(i);
    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u]) {
            indeg[v]--;
            if (indeg[v] == 0) q.push(v);
        }
    }
    if ((int)order.size() != n) cout << -1 << endl;
    else {
        for (int x : order) cout << x << " ";
        cout << endl;
    }
    return 0;
}
// 输入: 4 4 / 1 0 / 2 0 / 3 1 / 3 2
// 输出: 0 1 2 3

要点：注意邻接表建边方向——prerequisites 中 [a, b] 表示先 b 后 a，所以边是 b→a，不是 a→b。这是最常见的坑！

📝易错点提醒

建边方向搞反：题目给 [a, b] 通常表示"学 a 要先学 b"，边应该是 b→a，不是 a→b。
忘记判断环：输出节点数 ≠ 总节点数时一定有环，别漏了这个判断。
多解问题：拓扑序不唯一，题目说"字典序最小"就要用优先队列（小根堆）。
DAG 才能排：有环的图不存在拓扑序，暴力排会死循环（虽然 Kahn 算法不会，但 DFS 版本要注意）。
入度数组初始化：vector<int> indeg(n, 0) 别忘了初始化为 0。

📘拓扑排序

📖概念讲解

💻代码示例

🧩互动小测

Q1：拓扑排序只能用于哪种图？

Q2：如果拓扑排序输出的节点数少于总节点数，说明什么？

Q3：要求拓扑序"字典序最小"，应该用什么代替普通队列？

🏋️动手练一练

📝 编程练习

📝易错点提醒