修改递归方式实现的图的深度优先搜索（DFS）算法，将输出（访问）顶点信息的语句移到退出递归前（即执行输出语句后立刻退出递归）。采用修改后的算法遍历有向无环图 G，若输出结果中包含 G 中的全部顶点，则输出的顶点序列是 G 的（ ）。

DFS 图的遍历

A. 拓扑有序序列 B. 逆拓扑有序序列 C. 广度优先搜索序列 D. 深度优先搜索序列

[tag_link]

正确答案：B

DFS 对任意有向边 vᵢ→vⱼ，DFS 从 vᵢ 沿该边访问 vⱼ 时，必须先完成 vⱼ 及其后继的递归，才能回到 vᵢ。把输出语句放在退出递归前，就会先输出后继 vⱼ，再输出前驱 vᵢ。因此所有边的终点都排在起点之前，输出序列是逆拓扑有序序列，选 B；若把该完成序列逆序，才得到拓扑序。