题20

题20

题目

用 DFS 算法遍历一个无环有向图, 并在 DFS 算法退栈返回时输出相应的顶点, 则输出的顶点序列是 ( ).
A. 逆拓扑有序
B. 拓扑有序
C. 无序的
D. 无法确定

分析

沿着路径进入，进入到最深处输出打印，所以我觉得是逆拓扑序的

解

A
设图中有顶点 ,它有后继顶点 ,即存在边 。根据 DFS 的规则, 入栈后,必先遍历完其后继顶点后 才会出栈,也就是说 会在 之后出栈,在如题所指的过程中, 在 后打印。由于 和 具有任意性,因此由上面的规律看出,输出顶点的序列是逆拓扑有序序列。
对有向无环图利用深度优先搜索进行拓扑排序的例子如下: 如下图所示, 退出 DFS 栈的顺序为 efgdcahb, 此图的一个拓扑序列为 bhacdgfe。该方法的每一步均是先输出当前无后继的结点,即对每个结点 ,先递归地求出 的每个后继的拓扑序列。