拓扑排序适用于有向无环图，通过Kahn算法或DFS实现，用于确定节点线性序列以满足依赖关系，如课程安排或任务调度。
拓扑排序是图论中针对有向无环图（DAG）的一种线性排序算法，它能将图中的所有顶点排成一个序列，使得对于每一条有向边 (u, v)，u 在序列中都出现在 v 的前面。C++ 中实现拓扑排序主要有两种方法：基于深度优先搜索（DFS）和基于入度的 Kahn 算法。
1. 什么是拓扑排序？
拓扑排序只适用于有向无环图（DAG）。如果图中存在环，则无法进行拓扑排序，因为会出现逻辑矛盾（比如 A 必须在 B 前，B 又必须在 A 前）。
典型应用场景包括：
课程学习顺序安排 工程任务调度 编译依赖处理
2. 使用 Kahn 算法（基于入度）
Kahn 算法是一种广度优先的思想，通过不断移除入度为 0 的节点来构建拓扑序列。
立即学习“C++免费学习笔记（深入）”；
步骤如下：
计算每个节点的入度 将所有入度为 0 的节点加入队列 从队列中取出节点，加入结果序列，并将其邻居的入度减 1 若某邻居入度变为 0，则加入队列 重复直到队列为空
#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;}
3. 使用 DFS 实现拓扑排序
DFS 方法通过后序遍历的方式记录节点，然后逆序输出即为拓扑序列。
需要维护三个状态：
未访问（0） 正在访问（1，用于检测环） 已完成（2）
vector topo;vector visited;bool dfs(int u, vector<vector>& adj) { if (visited[u] == 1) return false; // 存在环 if (visited[u] == 2) return true; // 已完成 visited[u] = 1; for (int v : adj[u]) { if (!dfs(v, adj)) return false; } visited[u] = 2; topo.push_back(u); // 后序添加 return true;}vector topologicalSortDFS(int n, vector<vector>& adj) { visited.assign(n, 0); topo.clear(); for (int i = 0; i < n; i++) { if (visited[i] == 0) { if (!dfs(i, adj)) { return {}; // 存在环 } } } reverse(topo.begin(), topo.end()); return topo;}
4. 完整示例与测试
以下是一个完整可运行的例子：
int main() { int n = 6; vector<vector> adj(n); // 构建图：0→1, 0→2, 1→3, 2→3, 3→4, 4→5 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 result = topologicalSort(n, adj); if (result.empty()) { cout << "图中存在环，无法进行拓扑排序。n"; } else { cout << "拓扑排序结果："; for (int x : result) { cout << x << " "; } cout << endl; } return 0;}
输出结果应为：0 1 2 3 4 5，符合依赖关系。
基本上就这些。Kahn 算法更直观，适合初学者；DFS 方法更贴近递归思维，也便于检测环。根据实际需求选择即可。注意建图方式（邻接表）和边界处理，拓扑排序就能稳定运行。
以上就是C++怎么实现拓扑排序算法_C++图论与有向无环图(DAG)应用的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1486998.html
微信扫一扫 
支付宝扫一扫 
