8级 · 拓扑排序

📖 概念讲解

拓扑排序（Topological Sort）是对有向无环图（DAG）的所有顶点排出一个线性序列，使得对每条有向边 (u→v)，u 都排在 v 前面。简单说：谁被依赖，谁就排前面。

常见场景：课程先修关系、编译依赖、任务调度——"先修课 A 必须在 B 之前完成"。

核心思路：Kahn 算法（BFS 版）

1. 统计每个点的入度（有几条边指向它）
2. 把所有入度为 0 的点放进队列
3. 每次从队列取出一个点，它的所有邻居入度 -1
4. 邻居入度变成 0 就入队
5. 队列空了，如果处理的点数 = 总点数 → 成功；否则有环，排序失败

易错点：拓扑排序结果不唯一！多个入度为 0 的点，取哪个都合法。考试常考"判断是否有环"和"输出字典序最小的拓扑序"（用优先队列代替普通队列）。

💻 代码示例

// 拓扑排序 — Kahn 算法（BFS版）
// 输入：n 个点，m 条有向边
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;             // n=点数, m=边数
    cin >> n >> m;
    vector<vector<int>> adj(n + 1); // 邻接表存图
    vector<int> indeg(n + 1, 0);     // 每个点的入度

    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 = 1; 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]) {
            indeg[v]--;              // u 被处理了, v 入度-1
            if (indeg[v] == 0) q.push(v); // 入度变0, 可以排了
        }
    }

    if ((int)order.size() == n) {
        for (int x : order) cout << x << " ";
        cout << endl;
    } else cout << "存在环，无法拓扑排序" << endl;
}
// 输入: 6 6  →  1 2, 1 3, 2 4, 3 4, 4 5, 4 6
// 输出: 1 2 3 4 5 6 （或 1 3 2 4 5 6 等合法序列）

🧩 互动小测

📝 易错点提醒