拓扑排序用于有向无环图（dag），通过入度法或dfs法将顶点排成线性序列，使得每条有向边(u,v)中u在v之前。1. 入度法（kahn算法）基于贪心思想，计算各节点入度，将入度为0的节点入队，依次出队并更新邻接点入度，直至队列为空；若结果序列长度等于节点数，则存在有效拓扑排序，否则图含环。2. dfs法通过深度优先搜索，在回溯时将节点加入结果序列，需标记节点状态（未访问、访问中、已完成），若遍历中遇到“正在访问”的节点则说明有环，最后反转结果序列得到拓扑序。两种方法时间复杂度均为o(v+e)，kahn算法逻辑清晰适合初学者，dfs法适用于熟悉递归和状态标记的场景。正确性依赖于判断是否存在环，是实现拓扑排序的关键前提。
拓扑排序用于有向无环图（DAG），将图中所有顶点排成线性序列，使得对于每条有向边 (u, v)，u 在序列中都出现在 v 之前。C++ 中通常使用两种方法实现：入度法（Kahn 算法）和 DFS 法。
使用入度法（Kahn 算法）实现拓扑排序
该方法基于贪心思想：每次选择入度为 0 的节点加入结果序列，并删除其出边，更新邻接点的入度。
步骤如下：
- 计算每个节点的入度
- 将所有入度为 0 的节点加入队列
- 从队列中取出节点，加入结果序列
- 遍历该节点的所有邻接点，将其入度减 1；若入度变为 0，则加入队列
- 重复直到队列为空
如果最终结果序列长度等于节点数，则存在有效拓扑排序；否则图中有环。
立即学习“C++免费学习笔记（深入）”；
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> topologicalSort(int n, vector<vector<int>>& adj) {
vector<int> indegree(n, 0);
// 计算每个节点的入度
for (int u = 0; u < n; u++) {
for (int v : adj[u]) {
indegree[v]++;
}
}
queue<int> q;
// 将入度为 0 的节点入队
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) {
q.push(i);
}
}
vector<int> topo;
while (!q.empty()) {
int u = q.front();
q.pop();
topo.push_back(u);
// 遍历 u 的所有邻接点
for (int v : adj[u]) {
indegree[v]--;
if (indegree[v] == 0) {
q.push(v);
}
}
}
// 检查是否存在环
if (topo.size() != n) {
return {}; // 说明图中有环
}
return topo;
}
使用 DFS 实现拓扑排序
DFS 方法通过深度优先搜索，在回溯时将节点加入结果序列（逆序）。需要标记节点状态：未访问、正在访问、已完成。
核心逻辑：
- 对每个未访问节点调用 DFS
- 在 DFS 中，先标记当前节点为“正在访问”
- 递归访问所有邻接点；若遇到“正在访问”的节点，说明有环
- 回溯前将节点加入结果数组
- 最后反转数组得到拓扑序列
#include <iostream>
#include <vector>
using namespace std;
bool dfs(int u, vector<int>& state, vector<vector<int>>& adj, vector<int>& result) {
state[u] = 1; // 正在访问
for (int v : adj[u]) {
if (state[v] == 1) return false; // 发现环
if (state[v] == 0) {
if (!dfs(v, state, adj, result)) return false;
}
}
state[u] = 2; // 已完成
result.push_back(u);
return true;
}
vector<int> topologicalSortDFS(int n, vector<vector<int>>& adj) {
vector<int> state(n, 0); // 0:未访问, 1:访问中, 2:已完成
vector<int> result;
for (int i = 0; i < n; i++) {
if (state[i] == 0) {
if (!dfs(i, state, adj, result)) {
return {}; // 存在环
}
}
}
reverse(result.begin(), result.end());
return result;
}
完整测试示例
假设有一个包含 6 个节点的 DAG，边为：0→1, 0→2, 1→3, 2→3, 3→4, 4→5。
int main() {
int n = 6;
vector<vector<int>> adj(n);
// 添加边
adj[0].push_back(1);
adj[0].push_back(2);
adj[1].push_back(3);
adj[2].push_back(3);
adj[3].push_back(4);
adj[4].push_back(5);
vector<int> order = topologicalSort(n, adj);
// 或者使用：topologicalSortDFS(n, adj)
if (order.empty()) {
cout << "图中存在环，无法进行拓扑排序\n";
} else {
cout << "拓扑排序结果：";
for (int x : order) {
cout << x << " ";
}
cout << endl;
}
return 0;
}
输出可能为：0 1 2 3 4 5，具体顺序取决于算法实现和图结构。
基本上就这些。两种方法时间复杂度都是 O(V + E)，推荐初学者使用 Kahn 算法，逻辑清晰且易于理解。DFS 方法适合已有 DFS 基础的场景。注意判断环的存在是拓扑排序的关键前提。
