拓扑排序（Topological Sort） 题目描述：给定一个有向无环图（DAG），包含n个节点和m条有向边，要求返回一个节点的线性序列，使得对于图中的每一条有向边(u → v)，在序列中节点u都出现在节点v之前。如果存在多个合法序列，返回任意一个即可。如果图中存在环，则无法进行拓扑排序，应返回空数组。 解题过程： 理解核心概念 拓扑排序只适用于有向无环图（DAG）。核心要求是保持节点的"前后关系"：如果存在u → v的路径，那么u必须在v之前。这类似于任务依赖关系，必须先完成前置任务才能进行后续任务。 构建图的表示 通常使用邻接表来表示图： 创建一个列表 graph ， graph[i] 存储从节点i出发能直接到达的所有邻居节点 创建一个数组 inDegree ， inDegree[i] 记录指向节点i的边的数量（入度） 计算所有节点的入度 遍历图中的所有边，对于每条边u → v，将 inDegree[v] 加1。 Kahn算法实现步骤 这是基于BFS的拓扑排序算法： 将所有入度为0的节点加入队列（这些节点没有前置依赖） 当队列不为空时： 从队列中取出一个节点，加入结果序列 遍历该节点的所有邻居，将每个邻居的入度减1 如果某个邻居的入度变为0，将其加入队列 如果结果序列的长度等于节点总数，说明拓扑排序成功；否则说明图中存在环 详细示例 考虑有向图：0 → 1 → 2，0 → 3 节点0：入度=0 节点1：入度=1（来自0） 节点2：入度=1（来自1） 节点3：入度=1（来自0） 执行过程： 初始队列：[ 0 ]（入度为0） 处理0：结果[ 0]，1和3入度减为0，队列变为[ 1,3 ] 处理1：结果[ 0,1]，2入度减为0，队列变为[ 3,2 ] 处理3：结果[ 0,1,3]，队列变为[ 2 ] 处理2：结果[ 0,1,3,2 ] 合法拓扑序列：[ 0,1,3,2]或[ 0,3,1,2 ] 环检测 如果最终结果序列的长度小于节点总数，说明存在环（有些节点的入度永远无法变为0）。 算法复杂度 时间复杂度：O(n+m)，其中n是节点数，m是边数 空间复杂度：O(n+m)，用于存储图和入度信息 拓扑排序在任务调度、编译顺序确定、课程安排等问题中有广泛应用。