拓扑排序（Topological Sorting）是针对有向无环图（DAG）的一种顶点线性排序算法，其核心思想是：当图中存在一条从顶点u到顶点v的有向边时，在排序结果中u必须出现在v之前。拓扑排序广泛应用于任务调度、依赖解析、编译优化等场景，其常见实现方式包括Kahn算法（基于入度递减）和DFS深度优先遍历（基于递归后序）。执行拓扑排序时，首先统计所有顶点的入度，将入度为0的顶点加入队列，然后依次取出顶点并更新其邻接点的入度，重复此过程直到所有顶点都被处理；若最终仍有顶点剩余，则说明图中存在环，无法进行拓扑排序。该方法保证了依赖关系的严格顺序，是解决多步骤流程中前置条件问题的核心技术。

【常见问题】

问题1：拓扑排序只能用于有向无环图吗？如果图中存在环会怎样？

回答1：拓扑排序严格限定在有向无环图（DAG）中执行。如果图中存在环，则无法得到合法的拓扑排序结果，因为环内顶点之间存在循环依赖，无法确定谁先谁后。常见的Kahn算法在执行过程中，若最终仍有顶点入度不为0，即可判定图中存在环，此时拓扑排序失败。

问题2：拓扑排序和深度优先搜索（DFS）有什么关系？

回答2：拓扑排序可以通过DFS的递归后序实现。具体做法是：对图进行深度优先遍历，在每次递归返回前将当前顶点压入栈中，最后栈中顶点的逆序即为拓扑排序结果。这种方法需要额外的标记来检测环（如灰色节点），若发现后向边则说明存在环。

问题3：拓扑排序在实际开发中有哪些典型应用？

回答3：拓扑排序广泛应用于包管理工具（如npm、pip）的依赖解析、编译系统中的源文件编译顺序确定、任务调度系统中的作业执行顺序规划、以及课程安排中先修课程的顺序制定等。所有需要“先完成某任务才能进行另一任务”的场景，几乎都能借助拓扑排序解决。