在现实生活中，很多任务之间存在依赖关系。比如：你必须先学完 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 代码实现#includeiostream#includevector#includequeueusingnamespacestd;vectorinttopologicalSort(intn,vectorvectorintedges){// 构建邻接表和入度数组vectorvectorintgraph(n);vectorintinDegree(n,0);for(autoedge:edges){intfrom=edge[0];intto=edge[1];graph[from].push_back(to);inDegree[to]++;}// 将所有入度为 0 的顶点加入队列queueintq;for(inti=0;in;i++){if(inDegree[i]==0){q.push(i);}}vectorintresult;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: 高级算法vectorvectorintedges={{0,