从零到一，把拓扑排序“拆“给你看

很多人第一次接触「拓扑排序」，会被名字唬住 —— 听起来像是某种复杂的数值排序算法。但剥开概念外壳，它的本质极其朴素：给一组有依赖关系的任务，排出一个合法的执行顺序。所有前置任务必须排在后面任务的前面，不能出现循环依赖，也不能跳步。

拓扑排序知识全景

先通过思维导图快速建立全局框架，帮你理清所有核心模块：

标题

一、先破题：拓扑排序，排的不是大小，是依赖

核心定义

对一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点进行线性排序，满足： 对于图中任意一条有向边 u → v，顶点 u 在排序结果中一定出现在顶点 v 之前。

通俗翻译：

• u → v 代表「u 是 v 的前置条件」，比如 u 是先修课，v 是后续课
• 拓扑排序就是给所有任务排个队，保证做任何任务之前，它的所有前置任务都已经做完了

必要前提：必须是有向无环图

有环的图不存在合法拓扑序。 举个最简单的反例：A → B，B → A。A 要等 B 做完，B 也要等 A 做完，永远无法开始，这就是典型的循环依赖。

一个直观的生活例子

大学选课体系：

• 高数是线代的先修课：高数 → 线代
• 线代是矩阵论的先修课：线代 → 矩阵论
• C 语言是数据结构的先修课：C 语言 → 数据结构

合法的拓扑序可以是：高数 → C语言 → 线代 → 数据结构 → 矩阵论，也可以是C语言 → 高数 → 数据结构 → 线代 → 矩阵论。

注意：拓扑序不唯一，只要满足前置关系，都是合法的。

二、Kahn 算法：用「入度」推着任务走

这是最直观、最常用的拓扑排序实现，本质是广度优先搜索（BFS）的思路，靠「入度」驱动整个流程。

核心思想

一个节点的「入度」，就是指向它的边的数量，也就是它的前置任务个数。

• 入度为 0 = 没有前置任务，可以立刻执行
• 每完成一个任务，它所有后继任务的入度就减 1（少了一个前置）
• 当后继任务的入度减到 0，说明所有前置都做完了，可以开始执行

分步执行流程

算法步骤图解

下面用一张 5 节点的 DAG，完整演示 Kahn 算法的执行全过程：

代码实现 1：标准队列版（C++）

最通用的实现，邻接表存图，队列驱动 BFS，逻辑清晰不易写错。

cpp

运行

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

// n: 节点数（节点编号 0~n-1）
// edges: 有向边列表，每条边 u->v 代表 u 是 v 的前置
vector<int> topologicalSort_Kahn(int n, vector<vector<int>>& edges) {
vector<vector<int>> adj(n); // 邻接表
vector<int> inDegree(n, 0); // 入度数组

// 1. 建图 + 统计入度
for (auto& edge : edges) {
int u = edge[0], v = edge[1];
adj[u].push_back(v); // u -> v
inDegree[v]++;
}

queue<int> q;
// 2. 所有入度为0的节点入队
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) {
q.push(i);
}
}

vector<int> res;
// 3. BFS 核心流程
while (!q.empty()) {
int u = q.front();
q.pop();
res.push_back(u); // 加入拓扑序列

// 遍历所有后继，入度减1
for (int v : adj[u]) {
inDegree[v]–;
if (inDegree[v] == 0) {
q.push(v);
}
}
}

// 4. 判断是否有环：序列长度不等于节点数则存在环
if (res.size() != n) {
return {}; // 有环，返回空
}
return res;
}

代码实现 2：数组模拟队列（竞赛优化版）

在数据量较大时，用数组模拟队列比 STL 队列更快，减少内存分配开销，适合算法竞赛场景。

cpp

运行

vector<int> topologicalSort_Kahn_array(int n, vector<vector<int>>& edges) {
vector<vector<int>> adj(n);
vector<int> inDegree(n, 0);

for (auto& e : edges) {
adj[e[0]].push_back(e[1]);
inDegree[e[1]]++;
}

vector<int> q(n); // 数组模拟队列
int head = 0, tail = 0;

for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) {
q[tail++] = i;
}
}

while (head < tail) {
int u = q[head++];
for (int v : adj[u]) {
if (–inDegree[v] == 0) {
q[tail++] = v;
}
}
}

if (tail != n) return {};
// q数组前n个元素就是拓扑序
return vector<int>(q.begin(), q.begin() + n);
}

三、DFS 法：从最深处倒着推顺序

很多人疑惑：深度优先搜索怎么和拓扑排序扯上关系？核心玄机在于后序遍历的逆序。

核心思想

后序遍历的规则是：先遍历完所有子节点，再处理当前节点。 对应到依赖关系里：先把所有后继任务都处理完，再处理当前任务 —— 这刚好是拓扑序的反向。 因此，把后序遍历的结果反转过来，就是一个合法的拓扑序列。

关键：三色标记法检测环

DFS 实现拓扑排序必须标记节点的三种状态，用来检测环：

• 0：未访问过
• 1：访问中（当前在递归栈里）
• 2：已访问（所有后继都处理完了）

如果遍历过程中遇到了状态为 1 的节点，说明走着走着走回了当前路径上的节点 —— 图中存在环。

代码实现 3：DFS 递归版（C++）

cpp

运行

class TopoSort_DFS {
private:
vector<vector<int>> adj;
vector<int> state; // 0=未访问, 1=访问中, 2=已访问
vector<int> res;
bool hasCycle = false;

void dfs(int u) {
state[u] = 1; // 标记为访问中
for (int v : adj[u]) {
if (state[v] == 0) {
dfs(v);
if (hasCycle) return; // 发现环，提前返回
} else if (state[v] == 1) {
// 遇到访问中的节点，存在环
hasCycle = true;
return;
}
}
state[u] = 2; // 所有后继处理完，标记为已访问
res.push_back(u); // 后序位置加入结果
}

public:
vector<int> sort(int n, vector<vector<int>>& edges) {
adj.resize(n);
state.assign(n, 0);
res.clear();
hasCycle = false;

for (auto& e : edges) {
adj[e[0]].push_back(e[1]);
}

// 遍历所有节点，防止非连通图遗漏
for (int i = 0; i < n; i++) {
if (state[i] == 0) {
dfs(i);
if (hasCycle) return {};
}
}

// 后序结果反转，得到拓扑序
reverse(res.begin(), res.end());
return res;
}
};

四、横向 PK：两种算法怎么选？

结论：日常工程和刷题中，Kahn 算法用得更多，代码不易写错，环检测直观；DFS 法适合理解图的深度遍历本质，在一些图论综合题中更灵活。

五、落地：拓扑排序在真实世界里干嘛用？

拓扑排序不是纸上谈兵的算法，它是很多系统的底层核心：

六、踩坑预警：这几个地方最容易错

1. 拓扑序不唯一

只要满足前置关系，顺序就合法。不要默认只有一种正确结果。

2. 建图方向搞反

u 是 v 的前置 对应边 u → v，写反了入度统计全错，排序结果必然错误。

3. 忽略非连通图

图可能有多个独立分支，必须遍历所有节点，不能只从一个起点开始。

4. 有环图强行排序

有环图不存在拓扑序，必须做环检测，不能默认输入都是 DAG。

5. DFS 直接返回遍历顺序

必须是后序遍历的逆序，直接返回前序 / 后序都是错的。

七、上手练：经典例题完整实现

以 LeetCode 210. 课程表 II 为例，题目要求返回合法的上课顺序，是标准拓扑排序模板题。

题目大意

总共有 numCourses 门课，记为 0 到 numCourses-1。给你一个数组 prerequisites，其中 prerequisites[i] = [ai, bi] 表示要学 ai 必须先学 bi。请你返回一个合法的上课顺序，不存在则返回空数组。

代码实现 4：Kahn 算法题解

cpp

运行

vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> adj(numCourses);
vector<int> inDegree(numCourses, 0);

// 注意边的方向：先修bi -> ai
for (auto& p : prerequisites) {
int ai = p[0], bi = p[1];
adj[bi].push_back(ai);
inDegree[ai]++;
}

queue<int> q;
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) q.push(i);
}

vector<int> res;
while (!q.empty()) {
int u = q.front();
q.pop();
res.push_back(u);
for (int v : adj[u]) {
if (–inDegree[v] == 0) {
q.push(v);
}
}
}

return res.size() == numCourses ? res : vector<int>();
}

写在最后

拓扑排序本质上是「依赖关系」的具象化处理，核心只有一句话：前置不完成，后继不开始。 两种主流实现里，Kahn 算法靠入度做正向推进，DFS 靠后序逆序做反向推导，最终殊途同归，都是在 DAG 上找出一条合法的线性序列。

掌握它不仅能搞定算法题，更能帮你理解现实中所有依赖调度系统的底层逻辑。

谢谢