c++中如何实现拓扑排序_c++拓扑排序实现方法
最新回答
内谎言太羙。
2026-10-22 16:46:20
在C++中，拓扑排序用于有向无环图（DAG），可通过Kahn算法（基于入度）或DFS方法（基于后序遍历）实现。以下是具体实现方法及代码示例：
1. 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; // 入度为0的节点入队 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遍历图，记录节点的“完成时间”（即递归回溯时压栈的顺序），最终栈中元素从顶到底即为拓扑序。过程中通过递归栈检测环。
实现步骤：
- 对每个未访问的节点进行DFS。
- 递归访问所有邻接点后，将当前节点压入栈。
- 若在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); // 使用Kahn算法 vector<int> order = topoSortKahn(n, adj); if (!order.empty()) { cout << "Kahn算法拓扑排序结果："; for (int x : order) { cout << x << " "; } cout << endl; } // 使用DFS方法 order = topoSortDFS(n, adj); if (!order.empty()) { cout << "DFS方法拓扑排序结果："; for (int x : order) { cout << x << " "; } cout << endl; } return 0;}4. 方法对比- Kahn算法：
优点：直观，易于理解入度变化过程。
缺点：需要额外维护入度数组和队列。
- DFS方法：
优点：更贴近搜索本质，适合在检测环的同时构造拓扑序。
缺点：递归实现可能带来栈溢出风险（对于大规模图）。
根据实际场景选择合适的方法即可。
热门标签
