怎样写出拓扑序列

拓扑排序是一种常见的图论算法，用于确定有向无环图(Directed Acyclic Graph, DAG)中各个节点之间的一种线性顺序，使得每个节点在拓扑排序中出现的位置都满足该节点的所有前驱节点在此之前出现。在实际应用中，拓扑排序常用于通过图计算的先后顺序来进行任务调度。

那么，如何写出拓扑序列呢？以下从算法理论、应用实例和实际操作三个角度进行分析。

一、算法理论

1.1 Kahn算法

Kahn算法(Kahn's algorithm)是拓扑排序算法中最常见的一种。它的思路是不断找到入度为0的顶点，输出并移除该顶点及其相关的有向边，直到图中不再存在入度为0的顶点。若最终输出的顶点数小于图中顶点总数，则表示图中存在环路，无法进行拓扑排序。

1.2 DFS深度优先搜索

DFS深度优先搜索是另一种常见的拓扑排序算法。它的思路是通过递归地访问节点的方式来实现，先访问该节点的所有前驱结点，将其所有前驱节点全部标记为已访问，再将该节点加入序列中。由于DFS深度优先搜索需要计算节点的出度，因此需要在创建邻接表的同时计算每个节点的出度。

二、应用实例

2.1 任务调度

拓扑排序可用于任务调度，即将多个任务按照依赖关系拓扑排序后确定执行顺序。例如，在某个生产线上，生产线的某些模块需要在其他模块完成之后才能开始工作，那么就可以通过拓扑排序算法将这些模块安排好执行顺序。

2.2 词法分析器

在编译原理中，词法分析器需要根据文法中规定的优先级，确定标识符、关键字、运算符等的执行顺序。通过将文法表示为带有权值的图，并使用拓扑排序算法确定它们的执行顺序，可以有效地提高编译器的效率。

三、实际操作

3.1 维护入度表

在使用Kahn算法进行拓扑排序时，需要维护每个节点的入度。一种简便的方法是使用一个数组来记录入度，每次删除一个节点时，遍历与该节点相关的有向边，将所有尚未被删除的目标节点对应的入度减一。这种方法的时间复杂度为$O(|V|+|E|)$。

3.2 应用DFS深度优先搜索

在使用DFS深度优先搜索进行拓扑排序时，需要标记每个节点的状态。一种常见的方法是将节点的状态改为已访问视为1，刚构造表中代表未访问的初始值设为0. 通过遍历整个图，将该节点之前所有层级节点递归遍历，最终形成一个递归栈，倒序输出，就是该图的拓扑排序。