1. 算法概述
拓扑排序（Topological Sort）是对有向无环图（DAG, Directed Acyclic Graph） 的所有顶点进行线性排序，使得对于图中任意一条有向边 (u → v)，顶点 u 在排序中都出现在顶点 v 之前。拓扑排序是任务调度、依赖解析等问题的理论基础。如果图中存在环，则无法进行拓扑排序。
2. 核心思想
拓扑排序有两种经典实现方式：
- Kahn 算法（BFS + 入度表）：统计每个顶点的入度，每次将入度为 0 的顶点加入队列，然后移除该顶点并减少其邻居的入度。
- DFS 后序遍历：对图进行 DFS，在回溯时将顶点压入栈中，最终栈的逆序即为拓扑排序。
两种方法都能同时检测图中是否存在环：
- Kahn：若最终处理的顶点数 < V，则存在环。
- DFS：若在递归过程中遇到正在访问中的顶点（回溯标记），则存在环。
3. 算法步骤/伪代码
Kahn 算法（BFS）
Kahn(G):
indegree[V] = 0
for each edge (u -> v):
indegree[v]++
queue q
for each v where indegree[v] == 0:
q.push(v)
result = []
while q is not empty:
u = q.front(); q.pop()
result.add(u)
for each neighbor v of u:
indegree[v]--
if indegree[v] == 0:
q.push(v)
if result.size() < V:
return "有环"
return result
DFS 算法
DFS_Topo(G):
visited[V] = 0 // 0=未访问, 1=访问中, 2=已完成
stack stk
for each v in V:
if visited[v] == 0:
if dfs(v) == false:
return "有环"
reverse(stk) and return
function dfs(u):
visited[u] = 1
for each neighbor v of u:
if visited[v] == 0:
if dfs(v) == false: return false
else if visited[v] == 1:
return false // 发现环
visited[u] = 2
stk.push(u)
return true
4. C++ 代码实现
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
// ==================== Kahn 算法 (BFS + 入度表) ====================
vector<int> topologicalSortKahn(int V, const vector<vector<int>>& graph) {
vector<int> indegree(V, 0);
for (int u = 0; u < V; u++) {
for (int v : graph[u]) {
indegree[v]++;
}
}
queue<int> q;
for (int i = 0; i < V; i++) {
if (indegree[i] == 0) {
q.push(i);
}
}
vector<int> result;
while (!q.empty()) {
int u = q.front();
q.pop();
result.push_back(u);
for (int v : graph[u]) {
indegree[v]--;
if (indegree[v] == 0) {
q.push(v);
}
}
}
// 如果结果数量不等于 V，说明存在环
if ((int)result.size() != V) {
return {}; // 返回空数组表示有环
}
return result;
}
// ==================== DFS 后序遍历算法 ====================
enum State { UNVISITED = 0, VISITING = 1, VISITED = 2 };
bool dfsTopo(int u, const vector<vector<int>>& graph,
vector<State>& state, vector<int>& result) {
state[u] = VISITING;
for (int v : graph[u]) {
if (state[v] == VISITING) {
return false; // 发现环
}
if (state[v] == UNVISITED) {
if (!dfsTopo(v, graph, state, result)) {
return false;
}
}
}
state[u] = VISITED;
result.push_back(u); // 后序：回溯时加入
return true;
}
vector<int> topologicalSortDFS(int V, const vector<vector<int>>& graph) {
vector<State> state(V, UNVISITED);
vector<int> result;
for (int i = 0; i < V; i++) {
if (state[i] == UNVISITED) {
if (!dfsTopo(i, graph, state, result)) {
return {}; // 有环
}
}
}
// 后序遍历结果需要反转才是拓扑序
reverse(result.begin(), result.end());
return result;
}
// ==================== LeetCode 207: 课程表（检测能否完成所有课程） ====================
bool canFinish(int numCourses, const vector<vector<int>>& prerequisites) {
// prerequisites[i] = [a, b] 表示要先修 b 才能修 a，即 b -> a
vector<vector<int>> graph(numCourses);
vector<int> indegree(numCourses, 0);
for (const auto& pre : prerequisites) {
int course = pre[0];
int prerequisite = pre[1];
graph[prerequisite].push_back(course);
indegree[course]++;
}
queue<int> q;
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
q.push(i);
}
}
int completed = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
completed++;
for (int v : graph[u]) {
indegree[v]--;
if (indegree[v] == 0) {
q.push(v);
}
}
}
return completed == numCourses;
}
// ==================== 测试 ====================
int main() {
// 示例图：6 个顶点
// 5 -> 0, 5 -> 2, 4 -> 0, 4 -> 1, 2 -> 3, 3 -> 1
int V = 6;
vector<vector<int>> graph(V);
graph[5].push_back(0);
graph[5].push_back(2);
graph[4].push_back(0);
graph[4].push_back(1);
graph[2].push_back(3);
graph[3].push_back(1);
// Kahn 算法
vector<int> orderKahn = topologicalSortKahn(V, graph);
cout << "Kahn 拓扑排序: ";
if (orderKahn.empty()) {
cout << "图中存在环！" << endl;
} else {
for (int v : orderKahn) cout << v << " ";
cout << endl;
}
// 一种可能输出: 4 5 0 2 3 1
// DFS 算法
vector<int> orderDFS = topologicalSortDFS(V, graph);
cout << "DFS 拓扑排序: ";
if (orderDFS.empty()) {
cout << "图中存在环！" << endl;
} else {
for (int v : orderDFS) cout << v << " ";
cout << endl;
}
// ============ LeetCode 207 课程表测试 ============
int numCourses = 4;
vector<vector<int>> prerequisites = {
{1, 0}, // 先修 0 再修 1
{2, 1}, // 先修 1 再修 2
{3, 2} // 先修 2 再修 3
};
cout << "\n课程表测试 (无环): "
<< (canFinish(numCourses, prerequisites) ? "可以完成" : "无法完成")
<< endl;
// 有环的例子
vector<vector<int>> prerequisites2 = {
{1, 0},
{0, 1} // 0 和 1 互相依赖，形成环
};
cout << "课程表测试 (有环): "
<< (canFinish(2, prerequisites2) ? "可以完成" : "无法完成")
<< endl;
return 0;
}
运行示例
Kahn 拓扑排序: 4 5 0 2 3 1
DFS 拓扑排序: 5 4 2 3 1 0
课程表测试 (无环): 可以完成
课程表测试 (有环): 无法完成
注意：拓扑排序的结果不是唯一的，取决于建图方式和遍历顺序。只要满足"每条边的起点在终点之前"即可。
5. 复杂度分析
- 时间复杂度：O(V + E)
- 每个顶点入队/出队一次：O(V)
- 每条边被处理一次：O(E)
- 空间复杂度：O(V + E)
- 邻接表存储：O(V + E)
- 入度数组、队列、visited 数组：O(V)
6. 应用场景
| 场景 | 说明 |
|---|---|
| 课程安排 | 根据先修关系规划学习路径（LeetCode 207/210） |
| 编译依赖 | Makefile/构建系统中源文件的编译顺序 |
| 任务调度 | 存在前置依赖的任务执行顺序 |
| 包管理器 | npm/pip 等工具解析软件包依赖关系 |
| 死锁检测 | 检测资源分配图中的循环等待 |
| 指令调度 | 编译器中的指令重排优化 |
7. 经典例题
LeetCode 207. 课程表
题目描述：你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses-1。在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi]，表示如果要学习课程 ai 则必须先学习课程 bi。请你判断是否可能完成所有课程的学习。
解题思路：将课程看作顶点，先修关系看作有向边（bi → ai）。判断该有向图是否存在拓扑排序（即是否为 DAG）。
LeetCode 210. 课程表 II
题目描述：与 207 相同，但需要返回一个可行的学习顺序。如果不可能完成，返回空数组。
解题思路：直接用 Kahn 算法或 DFS 求出拓扑排序结果即可。
关键代码要点：
prerequisites[i] = [a, b]→ 建边b -> a- 统计入度、BFS 或 DFS 遍历
- 最后检查结果长度是否等于课程总数
