题41

题41

题目

【2020 统考真题】修改递归方式实现的图的深度优先搜索（DFS）算法，将输出（访问) 顶点信息的语句移到退出递归前 (即执行输出语句后立刻退出递归).
采用修改后的算法遍历有向无环图 ,若输出结果中包含 中的全部顶点,则输出的顶点序列是 的 ( ) .
A. 拓扑有序序列
B. 逆拓扑有序序列
C. 广度优先搜索序列
D 深度优先搜索序列

分析

根据题干所提供的信息可知:
①图 为有向无环图,因此一定存在拓扑序列和逆拓扑序列。
②DFS 的性质是顶点 的所有后继顶点 出栈后, 才会出栈。
③本题要求执行输出语句后立刻退出递归, 即执行完输出语句后立即出栈, 因此后进栈的顶点先输出,结合②不难得出只有输出顶点 的所有后继顶点 后, 才会输出。
综合上述分析, 输出的顶点序列是逆拓扑有序序列。

解

B