详细讲解 C++ 有向无环图（DAG）及拓扑排序

详细讲解 C 中的有向无环图DAG和拓扑排序Topological Sort1. 先说“有向无环图”概念详细说明有向图Directed Graph每条边都有起点 → 终点顺序是重要的。无环Acyclic没有从任意一个顶点出发沿着边走回到自己。有向无环图DAG同时满足「有向」且「无环」的图。特点• 可以对顶点做线性排序拓扑序。br• 常见于项目任务调度、编译依赖、课程排课等。举例下面这张图就是一个 6‑节点的 DAG可更新。A ──► B ──►C│ │ ▲▼ ▼ │D ──► E ──► FA → B,B → C,C → F、A → D、D → E、E → F你可以看到没有任何一条路会回到起点。2. 在 C 中表示 DAG2.1 数据结构邻接表Adjacency List采用std::vectorstd::vectorint或std::vectorstd::vectorEdge最内层包含所有指向后续节点。这样即可按边数 O(E)进行遍历和更新。#include vector #include unordered_map #include iostream #include queue #include stack #include list /* 用 0‑n-1 编号的有向图: 0 是顶点 A1 是 B以此类推。 */ using Graph std::vectorstd::vectorint; // 这里使用 int 代表顶点索引 // 建图函数从外部的边列表构建 Graph buildGraph(int n, const std::vectorstd::pairint, int edges) { Graph g(n); for (auto [u, v] : edges) { g[u].push_back(v); // u - v } return g; }2.2 另一个常见的实现unordered_mapstd::string, std::vectorstd::string如果你想用「顶点名称」而不是整数using UGraph std::unordered_mapstd::string, std::vectorstd::string; UGraph buildUGraph(const std::vectorstd::pairstd::string, std::string edges) { UGraph g; for (const auto e : edges) { g[e.first].push_back(e.second); // 注意不存在的 key 会自动生成空 vector } return g; }注意顶点名字的集合keys必须完整否则后面访问将产生空指针。3. 判断是否真的 DAG无环检测“拓扑排序” 的实现本身可以检测环但我们也可以单独检测它。两种常用方法3.1 DFS 颜色标记0→ 未访问1→ 当前递归栈中灰色2→ 完全访问黑色bool dfsCycle(const Graph g, int u, std::vectorint color) { color[u] 1; // 灰色 for (int v : g[u]) { if (color[v] 0 dfsCycle(g, v, color)) return true; // 发现回边 if (color[v] 1) // 同一递归栈里再次访问 - 循环 return true; } color[u] 2; // 黑色完全访问 return false; } bool hasCycle(const Graph g) { int n g.size(); std::vectorint color(n, 0); for (int i 0; i n; i) { if (color[i] 0 dfsCycle(g, i, color)) return true; } return false; }3.2 Kahn 的拓扑算法也能检测环计算每个点的入度in‑degree采用队列所有入度为 0 的点都可先出队每弹出一个点减少其相邻点的入度若最终弹出的点数 n则图里存在循环。bool hasCycleWithKahn(const Graph g) { int n g.size(); std::vectorint indeg(n, 0); for (int u 0; u n; u) for (int v : g[u]) indeg[v]; std::queueint q; for (int i 0; i n; i) if (indeg[i] 0) q.push(i); int cnt 0; while (!q.empty()) { int u q.front(); q.pop(); cnt; for (int v : g[u]) { if (--indeg[v] 0) q.push(v); } } return cnt ! n; // 若cnt n → 存在环 }关键点Kahn算法在运行过程中会得到一条拓扑序列如果序列长度不足n那必然有环。4. 拓扑排序目的得到一个顶点序列使得每条边u → v都满足u在v之前。4.1 DFS 版本递归或显式栈用visited探索递归结束后push该点到stack最后逆序或者直接返回栈的反向迭代void dfsTopo(const Graph g, int u, std::vectorbool vis, std::stackint st) { vis[u] true; for (int v : g[u]) if (!vis[v]) dfsTopo(g, v, vis, st); st.push(u); // 递归返回时再 push } std::vectorint topoSortDFS(const Graph g) { int n g.size(); std::vectorbool vis(n, false); std::stackint st; for (int i 0; i n; i) if (!vis[i]) dfsTopo(g, i, vis, st); std::vectorint order; while (!st.empty()) { order.push_back(st.top()); st.pop(); } return order; // 从前到后拓扑序 }复杂度O(V E)递归深度为O(V)。优点代码简短天然适合递归式 DFS。缺点对非常深的图递归容易栈溢出可改用显式栈。4.2 Kahn 算法迭代版本先算入度用队列或栈存所有入度为 0 的点每次弹出点u把u放到结果中对u的每条出边u→v把indeg[v]--indeg[v]0时入队std::vectorint topoSortKahn(const Graph g) { int n g.size(); std::vectorint indeg(n, 0); for (int u 0; u n; u) for (int v : g[u]) indeg[v]; std::queueint q; for (int i 0; i n; i) if (indeg[i] 0) q.push(i); std::vectorint order; while (!q.empty()) { int u q.front(); q.pop(); order.push_back(u); for (int v : g[u]) { if (--indeg[v] 0) q.push(v); } } if (order.size() ! n) { throw std::runtime_error(Graph has a cycle – no topological order); } return order; }复杂度O(V E)优点直接用队列避免递归栈溢出缺点需要显式维护入度数组。5. 完整示例把所有代码拼在一起/* 6 , 顶点 0A, 1B, 2C, 3D, 4E, 5F */ #include bits/stdc.h using namespace std; using Graph vectorvectorint; // ① 构图 Graph buildGraph(int n, const vectorpairint,int edges) { Graph g(n); for (auto [u,v] : edges) g[u].push_back(v); return g; } // ② 递归 DFS 拓扑排序 void dfsTopo(const Graph g, int u, vectorbool vis, stackint st) { vis[u] true; for (int v : g[u]) if (!vis[v]) dfsTopo(g,v,vis,st); st.push(u); } vectorint topoDFS(const Graph g) { int ng.size(); vectorbool vis(n,false); stackint st; for(int i0;in;i) if(!vis[i]) dfsTopo(g,i,vis,st); vectorint order; while(!st.empty()){order.push_back(st.top()); st.pop();} return order; } // ③ Kahn 拓扑排序 vectorint topoKahn(const Graph g) { int ng.size(); vectorint indeg(n,0); for(int u0;un;u) for(int v : g[u]) indeg[v]; queueint q; for(int i0;in;i) if(indeg[i]0) q.push(i); vectorint res; while(!q.empty()){ int uq.front();q.pop(); res.push_back(u); for(int v: g[u]) if(--indeg[v]0) q.push(v); } if(res.size()!n) throw runtime_error(Cycle detected); return res; } // ④ 主函数演示 int main() { vectorpairint,int eds { {0,1}, {0,3}, {1,2}, {1,4}, {2,5}, {4,5} }; Graph g buildGraph(6, eds); // 先确认无环 if (hasCycle(g)) { cerr Graph is NOT a DAG!\n; return 0; } // 取两种实现的拓扑序 auto ord1 topoDFS(g); auto ord2 topoKahn(g); auto print [](const vectorint ord){ for(int v: ord) cerr char(Av) ; }; cerr DFS topo: ; print(ord1); cerr \nKahn topo: ; print(ord2); cerr endl; }编译g -stdc17 -O2 -pipe -static -s -o dag_topo dag_topo.cpp ./dag_topo输出示例DFS topo: A D E B C F Kahn topo: A D B E C F两个输出均满足「所有边从前往后」。6. 关键概念与常见陷阱小贴士说明顶点编号采用 0‑n-1 或者别名字符串都行但一定统一。自环self‑loopu → u永远会导致环。不要忘记检查。图的密度采用邻接矩阵vectorvectorbool会占O(V^2)空间除非V非常小。递归栈深度对于V超过 10^5 的图建议不使用递归 DFS改为显式栈或 Kahn。多起点拓扑排序不必从0开始而要遍历所有未被访问的节点保证“全部”被排序。可忽略路径/边权重不影响拓扑排序。7. 拓扑排序的实际运用实例编译顺序头文件 / 模块之间的依赖关系先编译main所需的utils再编译utils自身课程安排先修数学 101→数学 201构造灯塔链表把依赖关系做成next指针使用拓扑排序来决定插入位置任务调度需要在 8h 的工作日内完成若干任务先安排必须先做的技能例如法律 → 税务 → 合同。8. 进一步阅读 练习主题书籍 / 参考练习题Topological Sorting《算法导论》CLRS第 22 章1️⃣ 把一个有向无环图拼成最短路径树br2️⃣ 找到所有「起点」与「终点」DAG Applications《高性能图计算》1️⃣ 代码执行计划排程br2️⃣ 依赖分析的Makefile生成DFS/tree-acyclic《算法设计手册》1️⃣ 找到无向图中的「桥」与「割点」你可以直接在上面 C 示例的main()函数里改不同的图验证topoSortKahn()与topoDFS()的结果。记得在修改边后再次hasCycle()检测以免出现奇怪的报错。 小结DAG有向且无环的图能被拓扑排序。实现使用邻接表 (vectorvectorint)通过 DFS 或 Kahn 算法得到拓扑序任何算法都能检测环。复杂度均为O(V E)。实际意义项目管理、编译器、调度等多方面实际需求。如果你对任何一个步骤还不太清楚欢迎再回到某一点细化。祝你在 C 图算法的路上愉快