【算法】小白也能懂 · 第 16 节：拓扑排序
在现实生活中，很多任务之间存在依赖关系。比如：你必须先学完 C++ 基础，才能学 STL；必须先编译源文件，才能链接成可执行程序。
拓扑排序就是解决这类「依赖关系排序」问题的经典算法。
1. 什么是拓扑排序？
1.1 问题定义
给定一个有向无环图（DAG），将图中的所有顶点排成一个线性序列，使得对于图中任意一条边 (u, v)，顶点 u 在序列中都出现在顶点 v 之前。
用大白话说：把有依赖关系的任务排个顺序，确保每个任务都在它依赖的任务之后执行。
1.2 生活中的例子
选课系统：
数据结构 → 算法设计 → 高级算法 ↓ ↓ 操作系统 → 编译原理这个依赖关系的拓扑排序结果可以是：
数据结构 → 操作系统 → 算法设计 → 编译原理 → 高级算法数据结构 → 算法设计 → 操作系统 → 编译原理 → 高级算法
注意：拓扑排序的结果可能不唯一，只要满足依赖关系即可。
1.3 关键性质
- 只有有向无环图（DAG）才有拓扑排序
- 如果图中有环，则不存在拓扑排序（循环依赖无法解决）
- 拓扑排序可以用来检测图中是否有环
2. Kahn 算法（BFS 方法）
2.1 核心思想
Kahn 算法的思路非常直观：
- 找到所有入度为 0的顶点（没有依赖的顶点）
- 将它们加入结果序列
- 从图中删除这些顶点和它们的边
- 重复步骤 1-3，直到所有顶点都被处理
如果最终结果包含所有顶点，则排序成功；如果还有剩余顶点，说明图中有环。
2.2 图解过程
假设有如下图：
5 → 0 ← 4 ↓ ↓ 2 → 3 → 1步骤 1：找到入度为 0 的顶点：5, 4
- 结果序列：[5, 4]
步骤 2：删除 5 和 4 的出边，更新入度
- 顶点 0 的入度从 2 变为 0
- 顶点 2 的入度从 1 变为 0
步骤 3：找到入度为 0 的顶点：0, 2
- 结果序列：[5, 4, 0, 2]
步骤 4：删除 0 和 2 的出边，更新入度
- 顶点 1 的入度从 1 变为 0
- 顶点 3 的入度从 1 变为 0
步骤 5：找到入度为 0 的顶点：1, 3
- 结果序列：[5, 4, 0, 2, 1, 3]
2.3 代码实现
#include<iostream>#include<vector>#include<queue>usingnamespacestd;vector<int>topologicalSort(intn,vector<vector<int>>&edges){// 构建邻接表和入度数组vector<vector<int>>graph(n);vector<int>inDegree(n,0);for(auto&edge:edges){intfrom=edge[0];intto=edge[1];graph[from].push_back(to);inDegree[to]++;}// 将所有入度为 0 的顶点加入队列queue<int>q;for(inti=0;i<n;i++){if(inDegree[i]==0){q.push(i);}}vector<int>result;while(!q.empty()){intnode=q.front();q.pop();result.push_back(node);// 删除该顶点的所有出边for(intneighbor:graph[node]){inDegree[neighbor]--;// 如果入度变为 0，加入队列if(inDegree[neighbor]==0){q.push(neighbor);}}}// 检测是否有环if(result.size()!=n){return{};// 有环，返回空数组}returnresult;}intmain(){// 示例：课程依赖关系// 0: 数据结构, 1: 算法设计, 2: 操作系统// 3: 编译原理, 4: 高级算法vector<vector<int>>edges={{0,