拓扑排序

前言：有先有后，怎么排个顺序？

大学生选课时，有些课有先修要求：必须先学微积分才能学概率论，必须先学编程基础才能学数据结构。如果你把这些课和先修关系画成一张图（“A 必须在 B 之前”就画 A → B 的箭头），那么一个合法的选课顺序就是这张图的一个拓扑排序。

不是所有图都能排出拓扑序。如果图里有环——比如”必须先学 A 才能学 B，必须先学 B 才能学 C，必须先学 C 才能学 A”——那就无解。拓扑排序只对**有向无环图（DAG）**有意义。

怎么求拓扑序？如果你已经学了 BFS，答案非常直觉：反复取出”没有未完成先修要求”的课，把它修掉，然后更新其他课的先修状态。这就是 Kahn 算法——本质上是 BFS 的一个变体。

这篇笔记会讲两种求拓扑序的方法（BFS 版和 DFS 版），并通过一道课程安排的例题展示实际应用。

拓扑排序

问题的本质

有向图中，若存在从 $u$ 到 $v$ 的路径，则 $u$ 必须排在 $v$ 前面。拓扑排序就是找到一个满足所有先后约束的线性序列。

前提条件：图必须有向无环（DAG）。有环就没法排出一个合法序列——环里每个点都要求在另一个前面，矛盾。

BFS 拓扑排序（Kahn 算法）

思路：不断取出入度为 0 的顶点（没有前置依赖），然后删掉它发出的边，更新邻居的入度。

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

vector<int> adj[MAXN];
int indeg[MAXN];

vector<int> toposort(int n) {
    vector<int> order;
    queue<int> q;

    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0) q.push(i);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u]) {
            if (--indeg[v] == 0)  // 删边后入度降为 0
                q.push(v);
        }
    }

    if ((int)order.size() != n) return {};  // 有环
    return order;
}

如果最终 order 的长度不足 $n$，说明有环，不存在拓扑序。

DFS 拓扑排序

后序遍历的反序就是拓扑序。因为 DFS 后序中，一个节点在所有它能到达的节点之后才被记录。

bool visited[MAXN];
bool onstack[MAXN];  // 环检测
vector<int> order;

bool dfs(int u) {
    visited[u] = true;
    onstack[u] = true;
    for (int v : adj[u]) {
        if (onstack[v]) return false;  // 发现环
        if (!visited[v] && !dfs(v)) return false;
    }
    onstack[u] = false;
    order.push_back(u);  // 后序：所有邻居处理完才记录自己
    return true;
}

最终 order 反转即为拓扑序。

复杂度

两种方法都是 $O(V + E)$。

例题：课程安排

$n$ 门课程，有 $m$ 条先修关系 $(u, v)$ 表示课程 $u$ 必须在 $v$ 之前修。给出一个合法的修课顺序。若存在环则输出 $-1$。

$1 \le n, m \le 10^5$

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

const int MAXN = 100006;
vector<int> adj[MAXN];
int indeg[MAXN];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        indeg[v]++;
    }

    vector<int> order;
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0) q.push(i);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u]) {
            if (--indeg[v] == 0)
                q.push(v);
        }
    }

    if ((int)order.size() != n) {
        printf("-1\n");
    } else {
        for (int i = 0; i < n; i++)
            printf("%d%c", order[i], i == n - 1 ? '\n' : ' ');
    }
    return 0;
}

解析：先修关系就是有向边，修课顺序就是拓扑序。BFS Kahn 算法每次取出当前没有未完成先修的课程，保证每门课修的时候所有先修都已修完。如果 order.size() < n 说明有循环依赖，不可能修完。当存在多个入度为 0 的点时，选哪个都行——如果题目要求字典序最小，把 queue 换成 priority_queue 即可。