会编程的土豆 • 计科学习者 个人主页 点击访问我的主页 核心专栏1 数据结构与算法 核心专栏2 LeetCode Hot 100✨ 面包会有的牛奶会有的一切都会有的拓扑排序一篇就够了从入门到精通你还在为课程安排、任务调度发愁吗拓扑排序就是你的救星什么是拓扑排序想象一下你要安排一学期的课程有些课必须先修其他课才能上微积分→线性代数→机器学习拓扑排序就是对DAG有向无环图的所有顶点进行线性排序使得对于每条边 u→vu 都出现在 v 之前。核心关键词DAG有向无环图Directed Acyclic Graph线性排序排成一列依赖关系谁必须在谁前面为什么需要拓扑排序应用场景具体问题拓扑排序的作用课程安排先修课依赖排出合理的学习顺序编译构建文件依赖确定编译顺序包管理依赖关系解决安装顺序️项目管理任务依赖制定项目计划 核心算法一Kahn算法入度法核心思想不断删除入度为0的节点就像剥洋葱一样层层剥开算法步骤1.计算每个节点的入度2.将入度为0的节点加入队列3.循环处理-取出队首节点加入结果-将它指向的节点入度减1-如果入度变为0加入队列4.判断结果数量节点总数#include iostream #include vector #include queue using namespace std; vectorint topologicalSortKahn(vectorvectorint graph, int n) { // 1. 计算入度 vectorint inDegree(n, 0); for (int u 0; u n; u) { for (int v : graph[u]) { inDegree[v]; } } // 2. 入度为0的节点入队 queueint q; for (int i 0; i n; i) { if (inDegree[i] 0) { q.push(i); } } // 3. 核心处理 vectorint result; while (!q.empty()) { int u q.front(); q.pop(); result.push_back(u); for (int v : graph[u]) { inDegree[v]--; if (inDegree[v] 0) { q.push(v); } } } // 4. 检查是否有环 if (result.size() ! n) { return {}; // 存在环 } return result; }执行过程图解初始图0──→1──→3│ └──→2──→3步骤1:入度[0]0→ 队列[0]步骤2:处理0解锁1和2→ 队列[1,2]步骤3:处理1解锁3入度3→1 → 队列[2]步骤4:处理2解锁3入度3→0 → 队列[3]步骤5:处理3→ 完成 结果:[0,1,2,3]✓核心算法二DFS算法深度优先核心思想沿着依赖链走到尽头回溯时记录节点算法步骤1.对每个未访问节点执行DFS2.DFS过程中-标记为访问中-递归访问所有邻居-发现访问中节点 → 存在环-回溯时压入栈3.栈反转得到拓扑序完整代码实现classTopologicalSortDFS{private:vectorvectorintgraph;vectorintvisited;// 0未访问, 1访问中, 2已完成stackintstk;bool hasCyclefalse;voiddfs(intu){visited[u]1;// 标记访问中for(intv:graph[u]){if(visited[v]1){// 发现环hasCycletrue;return;}if(visited[v]0){dfs(v);if(hasCycle)return;}}visited[u]2;// 标记完成stk.push(u);// 回溯时记录}public:vectorintsort(vectorvectorintg,intn){graphg;visited.assign(n,0);for(inti0;in;i){if(visited[i]0){dfs(i);if(hasCycle)return{};}}vectorintresult;while(!stk.empty()){result.push_back(stk.top());stk.pop();}returnresult;}};