拓扑排序

拓扑排序（Topological Sort）是对 有向无环图（DAG） 的顶点做线性排列：对每条有向边 $u\to v$，$u$ 都排在 $v$ 之前。若图中存在环，则不存在拓扑序。

本仓库提供两种经典实现——DFS 回溯 与 BFS / Kahn 入度法，均基于邻接表，时间复杂度 $O(V+E)$。

特性：时间 $O(V+E)$ · 空间 $O(V)$ · 仅适用于 DAG

源码：DFS 实现、BFS 实现

示例图

两份实现使用同一张 DAG 便于对比：

1 → 2 → 4 → 5
  ↘ 3 ↗

边集：$1\to 2,1\to 3,2\to 4,3\to 4,4\to 5$。合法拓扑序不唯一，例如 $1,2,3,4,5$ 或 $1,3,2,4,5$。

公共部分：邻接表

typedef struct Edge {
    int v;
    struct Edge* next;
} Edge;
 
Edge* G[maxn];

建边时将新边头插到 G[u]。BFS 版本在 add_edge 中额外维护 deg[v]++（入度）。

DFS 算法

思路

对每个未访问顶点递归 DFS，用三态标记检测环：

vis[u]	含义
0	未访问
1	正在访问（在当前递归栈上）
2	已完成

• 访问 u 时设为 1，递归所有后继。
• 若遇到 vis[v] == 1：说明 v 仍在 当前 DFS 递归栈 上（已设为 1，尚未回溯为 2）。此时边 $u\to v$ 指向栈中的祖先，形成 回边，例如路径 $v⇝u\to v$，故 有环。
• 若遇到 vis[v] == 2：说明 v 已在 另一条分支 中处理完毕并出栈。边 $u\to v$ 只是指向已完成的顶点（交叉边或前向边），不会沿当前路径回到栈内节点，不构成环，直接跳过即可。
• 所有后继处理完后设为 2，将 u 写入结果数组（按 完成时间 先后记录）。
• 最终 逆序 输出结果，即拓扑序。

核心代码

// 返回 0 表示存在环
int dfs(int u) {
    vis[u] = 1;  // 标记为「正在访问」，进入当前递归栈
 
    for (Edge* e = G[u]; e; e = e->next) {
        int v = e->v;
        if (vis[v] == 1) return 0;              // 回边：v 仍在栈上，有环
        if (vis[v] == 0 && !dfs(v)) return 0;   // 未访问则递归；vis[v]==2 则跳过
    }
 
    vis[u] = 2;       // 所有后继处理完，u 出栈
    topo[tp++] = u;   // 按完成时间记录（输出时需逆序）
    return 1;
}

对 $1\sim n$ 中每个 vis[i] == 0 的顶点调用 dfs(i)；任一调用返回 0 则整图有环。

运行结果

Topological order (DFS):
  1
  2
  3
  4
  5

BFS 算法（Kahn）

思路

维护每个顶点的 入度 deg[]（指向该顶点的边数）：

1. 入度为 0 的顶点入队：它们在当前剩余图中没有未处理的前驱，可以安全地排在最前面；初始时所有这样的顶点都入队。
2. 出队并「删边」：取出 u 写入结果，相当于将 u 从图中移除。遍历每条出边 $u\to v$，把 deg[v] 减 1，表示 u 这个前驱已处理完毕；若 deg[v] 变为 0，说明 v 的所有前驱都已输出，v 也可入队。
3. 判环：若队列为空时仍有顶点未输出（tp < n），说明剩余顶点各自都还有未处理的前驱——这些前驱彼此依赖、无法归零，即 存在环。DAG 中每一步至少能输出一个入度为 0 的顶点，因此无环时必有 tp == n。

本质是按「当前无前驱」的顺序逐层剥离，与 BFS 层序遍历结构相同，故也称 Kahn 算法。

核心代码

// 返回 0 表示存在环（tp < n）
int topo_sort_bfs(int n) {
    head = tail = 0;
    tp = 0;
 
    for (int i = 1; i <= n; i++) {
        if (deg[i] == 0) q[tail++] = i;  // 无前驱的顶点先入队
    }
 
    while (head < tail) {
        int u = q[head++];
        topo[tp++] = u;  // u 的所有前驱已输出，可写入结果
 
        for (Edge* e = G[u]; e; e = e->next) {
            int v = e->v;
            if (--deg[v] == 0) q[tail++] = v;  // 去掉前驱 u 后，v 无前驱则入队
        }
    }
 
    return tp == n;  // 未输出完说明剩余顶点构成环
}

结果按出队顺序直接输出，无需逆序。

运行结果

Topological order (BFS / Kahn):
  1
  3
  2
  4
  5

节点 2 与 3 互不依赖，BFS 按入队顺序可能先输出 3；两种结果均合法。

两种实现对比

	DFS	BFS / Kahn
核心结构	递归 + 三态 vis[]	入度 deg[] + 队列
环检测	遇到「正在访问」的后继	输出数 < n
结果顺序	逆序输出完成时间	直接按出队顺序
实现风格	与 DFS 遍历一脉相承	与 BFS / 层次遍历一脉相承
时间 / 空间	$O(V+E)$ / $O(V)$	$O(V+E)$ / $O(V)$

实际选型时：已有 DFS 框架、或需要顺带做 SCC 等 DFS 系列算法，用 DFS 版更自然；需要显式按入度逐层处理、或避免递归深度问题时，用 Kahn 版更直观。