拓扑排序序列怎么求

拓扑排序是图论中的一种排序方法，在有向无环图中，指定一种排序规则使得所有顶点被排列成线性序列，使得对于任何一条有向边 (u,v)，源点 u 都排在它的下游的终点 v 之前。这种排序方法很常见，并且经常用于解决排队问题和任务调度问题等。

拓扑排序的步骤：

1. 将图中所有入度为0的节点放入队列中，并标记为已访问。

2. 取出队列头部节点，将该节点所有邻接节点的入度减1。

3. 若有节点的入度为0，则放入队列中，并标记为已访问。

4. 重复 2 和 3 直到队列为空。

其中，最后的节点序列即为拓扑排序的结果。当然，如果图中存在环，那么就无法进行拓扑排序，这时候需要进行另外的处理。

常见的几种方法有：

1. Kahn 算法：Kahn 算法是一种经典算法，它使用一个队列来实现拓扑排序。每一次，从队头取出一个入度为 0 的顶点，然后删除以这个点为起点的所有有向边。当队列为空时，输出的顶点序列就是一种拓扑序列。如果队列为空时所有顶点都没有入度为 0 的顶点，说明图中存在环。

2. DFS 算法：DFS 算法实现拓扑排序，通过递归搜索图的方式实现。具体来说，对于当前结点 u，先对它的子结点进行深度优先遍历，若子结点在遍历的过程中未被访问过，那么就将子结点压入栈中。等到 u 的所有子结点都已经访问完毕之后，再将结点 u 压入栈中。最后栈中的序列就是一种拓扑序列。如果在搜索过程中遇到了访问过的结点，就说明图中有环。

3. 反向 DFS：反向 DFS 也是一种常见的实现方法。首先对原图进行反向得到反图，然后从某个结点出发进行 DFS。如果某个结点没有出度，那么就将其标记，并将其压入栈中。等到 DFS 完成之后，将栈中依次输出的结点组成的序列就是一种拓扑序列。如果在搜索过程中遇到了已经被标记的结点，那么就说明图中有环。

总之，对于有向无环图而言，拓扑排序是一个非常重要的算法。通过选择不同的实现方式，我们可以快速地求出图中所有结点的拓扑排序序列。当然，对于存在环的图，我们也需要特殊进行处理。