拓扑排序详解（Topological Sort）

拓扑排序详解（Topological Sort）

拓扑排序是对有向无环图（DAG）的顶点进行线性排序，使得对于每条有向边u → v，顶点u在排序中都出现在v之前。

一、Kahn 算法（BFS 版本）

算法核心

Kahn 算法的核心是用队列维护一个入度为 0 的节点集合，不断"剥离"这些节点，类似于"剥洋葱"思想。

算法流程

1. 初始化：统计所有节点的入度，将入度为 0 的节点入队
2. 循环剥离：
   • 从队列取出一个节点u，加入拓扑序列
   • 删除从u出发的所有边（即u的所有邻接点入度减 1）
   • 如果某个邻接点的入度变为 0，将其入队
3. 判断结果：
   • 如果拓扑序列长度等于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还未输出，说明有环！❌

完整代码

#include<bits/stdc++.h>usingnamespacestd;constintN=100005;vector<int>g[N],tp;intdu[N];// 入度数组intn,m;booltopo(){queue<int>q;// 1. 入度为0的点入队for(inti=1;i<=n;i++){if(du[i]==0)q.push(i);}// 2. 不断删除入度为0的点while(!q.empty()){intu=q.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);cin>>n>>m;for(inti=1;i<=m;i++){intu,v;cin>>u>>v;g[u].push_back(v);du[v]++;// v 的入度+1}if(!topo()){cout<<-1<<endl;}else{for(inti=0;i<tp.size();i++){cout<<tp[i]<<" ";}cout<<endl;}return0;}

复杂度分析

• 时间复杂度：O(n + m)，每个点入队一次，每条边被遍历一次
• 空间复杂度：O(n + m)

优缺点

二、DFS 算法（三色标记法）

算法核心

DFS 版本的核心是深度优先搜索 + 三色标记，利用递归栈来判断是否存在环。

颜色定义

• 白色（0）：未访问
• 灰色（-1）：正在访问中（在递归栈里）
• 黑色（1）：已访问完毕

算法流程

1. 对每个未访问的节点执行 DFS
2. DFS 过程中：
   • 将当前节点标记为灰色（正在访问）
   • 遍历所有邻接点：
     • 如果邻接点是灰色 → 说明有环（遇到了祖先节点）
     • 如果邻接点是白色 → 递归访问
   • 访问完毕后，将当前节点标记为黑色，并加入拓扑序列
3. 最后将拓扑序列反转（因为 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] ✅

完整代码

#include<bits/stdc++.h>usingnamespacestd;constintN=100005;vector<int>g[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(inti=1;i<=n;i++){if(!vis[i]){if(!dfs(i)){returnfalse;}}}reverse(tp.begin(),tp.end());// 反转得到拓扑序returntrue;}intmain(){ios::sync_with_stdio(false);cin.tie(0);cin>>n>>m;for(inti=1;i<=m;i++){intu,v;cin>>u>>v;g[u].push_back(v);}if(!topo()){cout<<-1<<endl;}else{for(inti=0;i<tp.size();i++){cout<<tp[i]<<" ";}cout<<endl;}return0;}

为什么 DFS 要反转？

因为 DFS 是后序记录：先访问所有子节点，再记录当前节点。这导致记录的序列是"从叶子到根"的顺序，需要反转才能得到"从根到叶子"的拓扑序。

后序记录：[叶子, ..., 根] 反转后： [根, ..., 叶子] ← 拓扑序

复杂度分析

• 时间复杂度：O(n + m)，每个点访问一次，每条边遍历一次
• 空间复杂度：O(n + m)

优缺点

三、两种算法对比

四、常见应用场景

1. 课程安排：判断能否修完所有课程
2. 编译依赖：确定文件编译顺序
3. 任务调度：确定任务执行顺序
4. 解决依赖关系：如包管理器安装顺序

五、优化技巧

1. 字典序最小的拓扑序

使用优先队列代替普通队列：

priority_queue<int,vector<int>,greater<int>>q;// 小根堆

2. 大数据的 DFS 防爆栈

使用非递归 DFS或增大栈空间，或改用 Kahn 算法。

3. 多组数据

每次重置数组和邻接表即可。

希望这篇博客对大家有所帮助！如有错误或建议，欢迎留言指正！📝完结撒花！！