拓扑排序用于有向无环图，确保每条边的起点在序列中位于终点之前。C++中常用Kahn算法和DFS方法实现：1. Kahn算法通过维护入度队列，依次输出入度为0的节点，更新邻接点入度，直至队列为空，若结果包含所有节点则排序成功，否则图含环；2. DFS方法对每个未访问节点进行深度优先搜索，在回溯时将节点压栈，最终出栈顺序即为拓扑序，过程中通过递归栈检测环。两种方法均可有效实现拓扑排序，Kahn更直观，DFS更贴近搜索本质。
拓扑排序用于有向无环图（DAG），将图中所有顶点排成线性序列，使得对于每条有向边 (u, v)，u 在序列中都出现在 v 之前。C++ 中常用两种方法实现：基于入度的 Kahn 算法 和 基于 DFS 的方法。
1. Kahn 算法（基于入度）
Kahn 算法通过不断选择入度为 0 的节点加入结果序列，并删除其出边，更新邻接点的入度。
步骤：
- 计算每个节点的入度
- 将所有入度为 0 的节点加入队列
- 从队列取节点，加入结果，遍历其邻接点，入度减 1；若减为 0 则入队
- 重复直到队列为空
- 若结果中节点数等于总节点数，则存在拓扑序；否则图中有环
#include <iostream> #include <vector> #include <queue> using namespace std; vector<int> topoSortKahn(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; for (int i = 0; i < n; 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 : adj[u]) { indegree[v]--; if (indegree[v] == 0) { q.push(v); } } } if (result.size() != n) { cout << "图中存在环，无法进行拓扑排序n"; return {}; } return result; }
2. DFS 方法（基于后序遍历）
利用 DFS 遍历图，记录节点的“完成时间”，完成后按逆序输出即为拓扑序。
立即学习“C++免费学习笔记（深入）”；
思路：
- 对每个未访问的节点进行 DFS
- 递归访问其所有邻接点后，将当前节点压入栈
- 最后栈中元素从顶到底即为拓扑序
#include <iostream> #include <vector> #include <stack> using namespace std; bool dfs(int u, vector<bool>& visited, vector<bool>& recStack, stack<int>& st, vector<vector<int>>& adj) { if (!visited[u]) { visited[u] = true; recStack[u] = true; for (int v : adj[u]) { if (!visited[v] && dfs(v, visited, recStack, st, adj)) return true; if (recStack[v]) return true; // 发现环 } } recStack[u] = false; st.push(u); return false; } vector<int> topoSortDFS(int n, vector<vector<int>>& adj) { vector<bool> visited(n, false); vector<bool> recStack(n, false); stack<int> st; for (int i = 0; i < n; i++) { if (!visited[i] && dfs(i, visited, recStack, st, adj)) { cout << "图中存在环n"; return {}; } } vector<int> result; while (!st.empty()) { result.push_back(st.top()); st.pop(); } return result; }
3. 使用示例
假设图有 6 个节点，边为：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 = topoSortKahn(n, adj); // 或者使用 topoSortDFS(n, adj) if (!order.empty()) { cout << "拓扑排序结果："; for (int x : order) { cout << x << " "; } cout << endl; } return 0; } 基本上就这些。Kahn 算法更直观，适合理解入度变化；DFS 方法更贴近搜索本质，适合检测环的同时构造顺序。根据实际场景选择即可。