拓扑排序用于有向无环图（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++免费学习笔记（深入）”；
// 示例代码：Kahn 算法实现拓扑排序
#include #include #include using namespace std;vector topologicalSort(int n, vector<vector>& adj) { vector indegree(n, 0); // 计算每个节点的入度 for (int u = 0; u < n; u++) { for (int v : adj[u]) { indegree[v]++; } } queue q; // 将入度为 0 的节点入队 for (int i = 0; i < n; i++) { if (indegree[i] == 0) { q.push(i); } } vector 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 中，先标记当前节点为“正在访问” 递归访问所有邻接点；若遇到“正在访问”的节点，说明有环 回溯前将节点加入结果数组 最后反转数组得到拓扑序列// 示例代码：DFS 实现拓扑排序
#include #include using namespace std;bool dfs(int u, vector& state, vector<vector>& adj, vector& 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 topologicalSortDFS(int n, vector<vector>& adj) { vector state(n, 0); // 0:未访问, 1:访问中, 2:已完成 vector 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> 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 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 基础的场景。注意判断环的存在是拓扑排序的关键前提。
以上就是C++如何实现拓扑排序_C++有向无环图(DAG)的拓扑排序算法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1485403.html
微信扫一扫 
支付宝扫一扫 
