拓扑排序详解Topological Sort拓扑排序是对有向无环图DAG的顶点进行线性排序使得对于每条有向边u → v顶点u在排序中都出现在v之前。一、Kahn 算法BFS 版本算法核心Kahn 算法的核心是用队列维护一个入度为 0 的节点集合不断剥离这些节点类似于剥洋葱思想。算法流程初始化统计所有节点的入度将入度为 0 的节点入队循环剥离从队列取出一个节点u加入拓扑序列删除从u出发的所有边即u的所有邻接点入度减 1如果某个邻接点的入度变为 0将其入队判断结果如果拓扑序列长度等于n说明存在拓扑排序无环否则图中存在环无法拓扑排序图解示例假设图如下入度统计 点1入度0 点2入度3来自1、3、4 点3入度0 点4入度0 点5入度2来自2、6 点6入度1来自4执行过程初始队列[1, 3, 4] 弹出4 → 删除4→2, 4→6 → 点6入度变0 → 队列[1, 3, 6] 弹出1 → 删除1→2 → 点2入度变2 → 队列[3, 6] 弹出3 → 删除3→2 → 点2入度变1 → 队列[6] 弹出6 → 删除6→5 → 点5入度变1 → 队列[]这时队列为空但点2和点5还未输出说明有环❌完整代码#includebits/stdc.husingnamespacestd;constintN100005;vectorintg[N],tp;intdu[N];// 入度数组intn,m;booltopo(){queueintq;// 1. 入度为0的点入队for(inti1;in;i){if(du[i]0)q.push(i);}// 2. 不断删除入度为0的点while(!q.empty()){intuq.front();q.pop();tp.push_back(u);for(intv:g[u]){du[v]--;// 删除边 u→vif(du[v]0){q.push(v);}}}// 3. 判断是否有环returntp.size()n;}intmain(){ios::sync_with_stdio(false);cin.tie(0);cinnm;for(inti1;im;i){intu,v;cinuv;g[u].push_back(v);du[v];// v 的入度1}if(!topo()){cout-1endl;}else{for(inti0;itp.size();i){couttp[i] ;}coutendl;}return0;}复杂度分析时间复杂度O(n m)每个点入队一次每条边被遍历一次空间复杂度O(n m)优缺点优点缺点直观易懂实现简单需要记录入度适合求字典序最小的拓扑序改用优先队列需要额外空间存储队列可以同时检测环只能处理有向图二、DFS 算法三色标记法算法核心DFS 版本的核心是深度优先搜索 三色标记利用递归栈来判断是否存在环。颜色定义白色0未访问灰色-1正在访问中在递归栈里黑色1已访问完毕算法流程对每个未访问的节点执行 DFSDFS 过程中将当前节点标记为灰色正在访问遍历所有邻接点如果邻接点是灰色 → 说明有环遇到了祖先节点如果邻接点是白色 → 递归访问访问完毕后将当前节点标记为黑色并加入拓扑序列最后将拓扑序列反转因为 DFS 是后序记录图解示例图1→2, 3→2, 4→2, 2→5, 6→5, 4→6 从1开始 1(灰色) → 2(灰色) → 5(灰色) → 5(黑色) → 2(黑色) → 1(黑色) 从3开始 3(灰色) → 2(已黑色跳过) → 3(黑色) 从4开始 4(灰色) → 2(已黑色) → 6(灰色) → 5(已黑色) → 6(黑色) → 4(黑色) 后序记录[5, 2, 1, 3, 6, 4] 反转后[4, 6, 3, 1, 2, 5] ✅完整代码#includebits/stdc.husingnamespacestd;constintN100005;vectorintg[N],tp;intvis[N];// 0未访问, -1访问中, 1已访问intn,m;booldfs(intu){vis[u]-1;// 标记为正在访问for(intv:g[u]){if(vis[v]-1){returnfalse;// 发现环}elseif(!vis[v]){if(!dfs(v)){returnfalse;}}}vis[u]1;// 标记为已访问tp.push_back(u);// 后序记录returntrue;}booltopo(){memset(vis,0,sizeof(vis));for(inti1;in;i){if(!vis[i]){if(!dfs(i)){returnfalse;}}}reverse(tp.begin(),tp.end());// 反转得到拓扑序returntrue;}intmain(){ios::sync_with_stdio(false);cin.tie(0);cinnm;for(inti1;im;i){intu,v;cinuv;g[u].push_back(v);}if(!topo()){cout-1endl;}else{for(inti0;itp.size();i){couttp[i] ;}coutendl;}return0;}为什么 DFS 要反转因为 DFS 是后序记录先访问所有子节点再记录当前节点。这导致记录的序列是从叶子到根的顺序需要反转才能得到从根到叶子的拓扑序。后序记录[叶子, ..., 根] 反转后 [根, ..., 叶子] ← 拓扑序复杂度分析时间复杂度O(n m)每个点访问一次每条边遍历一次空间复杂度O(n m)优缺点优点缺点不需要额外记录入度递归可能栈溢出n大时需改非递归代码简洁需要理解三色标记天然检测环反转操作需要注意三、两种算法对比对比维度Kahn 算法 (BFS)DFS 算法核心思想维护入度为0的节点集合三色标记 递归回溯数据结构队列或优先队列递归栈是否需要反转❌ 不需要✅ 需要环检测拓扑序列长度 n遇到灰色节点字典序最小✅ 改用优先队列即可❌ 不易实现空间占用O(n) 额外空间O(n) 递归栈适用场景直观易理解递归思维代码简洁四、常见应用场景课程安排判断能否修完所有课程编译依赖确定文件编译顺序任务调度确定任务执行顺序解决依赖关系如包管理器安装顺序五、优化技巧1. 字典序最小的拓扑序使用优先队列代替普通队列priority_queueint,vectorint,greaterintq;// 小根堆2. 大数据的 DFS 防爆栈使用非递归 DFS或增大栈空间或改用 Kahn 算法。3. 多组数据每次重置数组和邻接表即可。希望这篇博客对大家有所帮助如有错误或建议欢迎留言指正完结撒花
拓扑排序详解Topological Sort拓扑排序是对有向无环图DAG的顶点进行线性排序使得对于每条有向边u → v顶点u在排序中都出现在v之前。一、Kahn 算法BFS 版本算法核心Kahn 算法的核心是用队列维护一个入度为 0 的节点集合不断剥离这些节点类似于剥洋葱思想。算法流程初始化统计所有节点的入度将入度为 0 的节点入队循环剥离从队列取出一个节点u加入拓扑序列删除从u出发的所有边即u的所有邻接点入度减 1如果某个邻接点的入度变为 0将其入队判断结果如果拓扑序列长度等于n说明存在拓扑排序无环否则图中存在环无法拓扑排序图解示例假设图如下入度统计 点1入度0 点2入度3来自1、3、4 点3入度0 点4入度0 点5入度2来自2、6 点6入度1来自4执行过程初始队列[1, 3, 4] 弹出4 → 删除4→2, 4→6 → 点6入度变0 → 队列[1, 3, 6] 弹出1 → 删除1→2 → 点2入度变2 → 队列[3, 6] 弹出3 → 删除3→2 → 点2入度变1 → 队列[6] 弹出6 → 删除6→5 → 点5入度变1 → 队列[]这时队列为空但点2和点5还未输出说明有环❌完整代码#includebits/stdc.husingnamespacestd;constintN100005;vectorintg[N],tp;intdu[N];// 入度数组intn,m;booltopo(){queueintq;// 1. 入度为0的点入队for(inti1;in;i){if(du[i]0)q.push(i);}// 2. 不断删除入度为0的点while(!q.empty()){intuq.front();q.pop();tp.push_back(u);for(intv:g[u]){du[v]--;// 删除边 u→vif(du[v]0){q.push(v);}}}// 3. 判断是否有环returntp.size()n;}intmain(){ios::sync_with_stdio(false);cin.tie(0);cinnm;for(inti1;im;i){intu,v;cinuv;g[u].push_back(v);du[v];// v 的入度1}if(!topo()){cout-1endl;}else{for(inti0;itp.size();i){couttp[i] ;}coutendl;}return0;}复杂度分析时间复杂度O(n m)每个点入队一次每条边被遍历一次空间复杂度O(n m)优缺点优点缺点直观易懂实现简单需要记录入度适合求字典序最小的拓扑序改用优先队列需要额外空间存储队列可以同时检测环只能处理有向图二、DFS 算法三色标记法算法核心DFS 版本的核心是深度优先搜索 三色标记利用递归栈来判断是否存在环。颜色定义白色0未访问灰色-1正在访问中在递归栈里黑色1已访问完毕算法流程对每个未访问的节点执行 DFSDFS 过程中将当前节点标记为灰色正在访问遍历所有邻接点如果邻接点是灰色 → 说明有环遇到了祖先节点如果邻接点是白色 → 递归访问访问完毕后将当前节点标记为黑色并加入拓扑序列最后将拓扑序列反转因为 DFS 是后序记录图解示例图1→2, 3→2, 4→2, 2→5, 6→5, 4→6 从1开始 1(灰色) → 2(灰色) → 5(灰色) → 5(黑色) → 2(黑色) → 1(黑色) 从3开始 3(灰色) → 2(已黑色跳过) → 3(黑色) 从4开始 4(灰色) → 2(已黑色) → 6(灰色) → 5(已黑色) → 6(黑色) → 4(黑色) 后序记录[5, 2, 1, 3, 6, 4] 反转后[4, 6, 3, 1, 2, 5] ✅完整代码#includebits/stdc.husingnamespacestd;constintN100005;vectorintg[N],tp;intvis[N];// 0未访问, -1访问中, 1已访问intn,m;booldfs(intu){vis[u]-1;// 标记为正在访问for(intv:g[u]){if(vis[v]-1){returnfalse;// 发现环}elseif(!vis[v]){if(!dfs(v)){returnfalse;}}}vis[u]1;// 标记为已访问tp.push_back(u);// 后序记录returntrue;}booltopo(){memset(vis,0,sizeof(vis));for(inti1;in;i){if(!vis[i]){if(!dfs(i)){returnfalse;}}}reverse(tp.begin(),tp.end());// 反转得到拓扑序returntrue;}intmain(){ios::sync_with_stdio(false);cin.tie(0);cinnm;for(inti1;im;i){intu,v;cinuv;g[u].push_back(v);}if(!topo()){cout-1endl;}else{for(inti0;itp.size();i){couttp[i] ;}coutendl;}return0;}为什么 DFS 要反转因为 DFS 是后序记录先访问所有子节点再记录当前节点。这导致记录的序列是从叶子到根的顺序需要反转才能得到从根到叶子的拓扑序。后序记录[叶子, ..., 根] 反转后 [根, ..., 叶子] ← 拓扑序复杂度分析时间复杂度O(n m)每个点访问一次每条边遍历一次空间复杂度O(n m)优缺点优点缺点不需要额外记录入度递归可能栈溢出n大时需改非递归代码简洁需要理解三色标记天然检测环反转操作需要注意三、两种算法对比对比维度Kahn 算法 (BFS)DFS 算法核心思想维护入度为0的节点集合三色标记 递归回溯数据结构队列或优先队列递归栈是否需要反转❌ 不需要✅ 需要环检测拓扑序列长度 n遇到灰色节点字典序最小✅ 改用优先队列即可❌ 不易实现空间占用O(n) 额外空间O(n) 递归栈适用场景直观易理解递归思维代码简洁四、常见应用场景课程安排判断能否修完所有课程编译依赖确定文件编译顺序任务调度确定任务执行顺序解决依赖关系如包管理器安装顺序五、优化技巧1. 字典序最小的拓扑序使用优先队列代替普通队列priority_queueint,vectorint,greaterintq;// 小根堆2. 大数据的 DFS 防爆栈使用非递归 DFS或增大栈空间或改用 Kahn 算法。3. 多组数据每次重置数组和邻接表即可。希望这篇博客对大家有所帮助如有错误或建议欢迎留言指正完结撒花
![[光学原理与应用-521]：对光的错误理解与纠偏](http://pic.xiahunao.cn/yaotu/[光学原理与应用-521]：对光的错误理解与纠偏)
