拓扑排序适用于哪些图？

拓扑排序是一种线性排序算法，适用于有向无环图（Directed Acyclic Graph，简称DAG）。在有向无环图中，每个节点代表一个任务或事件，而每条有向边代表任务之间的依赖关系。拓扑排序的目标是找到一个线性序列，使得对于图中任意两个节点u和v，如果存在从u到v的有向边，那么在序列中u出现在v之前。

拓扑排序适用于以下类型的图：

1. 有向无环图（DAG）：这是拓扑排序最基本的应用场景。在有向无环图中，由于不存在环，因此可以保证任务之间的依赖关系是合理的，不会出现循环依赖，从而可以找到一个有效的线性排序。

2. 依赖关系图：在许多实际应用中，任务或事件之间存在依赖关系，例如在项目管理中，某些任务必须在其他任务完成后才能开始。拓扑排序可以用来确定这些任务的执行顺序，确保所有依赖关系得到满足。

3. 课程表安排：在大学的课程安排中，某些课程可能有先修课程的要求。拓扑排序可以帮助安排课程顺序，确保所有先修课程在后续课程之前完成。

4. 任务调度：在计算机操作系统和任务调度中，拓扑排序可以用来安排任务的执行顺序，确保任务之间的依赖关系得到满足，从而提高系统的效率和性能。

5. 编译器中的依赖分析：在编译器中，拓扑排序可以用来分析源代码中的依赖关系，确定变量和函数的声明顺序，以便正确地处理作用域和可见性。

拓扑排序的基本算法步骤如下：

1. 计算每个节点的入度：入度表示有多少条有向边指向该节点。
2. 选择入度为0的节点：这些节点没有依赖关系，可以作为线性序列的开始。
3. 将选中的节点加入线性序列：并从图中移除该节点及其所有出边。
4. 更新剩余节点的入度：对于被移除节点的邻接节点，其入度减1。
5. 重复步骤2-4，直到所有节点都被处理。

如果最终图中所有节点都被成功排序，则说明原图是一个有向无环图。如果存在未处理的节点，则说明图中存在环，无法进行拓扑排序。