题目

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

错因

A

记反了"DFS 出栈时输出 = 拓扑序"。其实正好相反——DFS 出栈（退出递归前）输出得到的是逆拓扑序，再翻转一下才是拓扑序。错因常见于把"基于 DFS 的拓扑排序算法"机械记成"DFS 退出时入栈，最后出栈即拓扑序"，而忽略了"出栈才是逆拓扑"。

C

完全没看清"递归 DFS"这几个字，把题目当成 BFS。BFS 用队列层层扩展，与递归无关；这里明确说的是"递归方式实现的 DFS"，输出顺序的依据是递归栈的进出，与 BFS 无关。

D

漏了"将输出语句移到退出递归前"这个关键修改。原始 DFS（进入递归就输出）输出的才是 DFS 序列；修改后变成退出递归才输出，得到的就不再是 DFS 序了——而是逆拓扑序。

总解析

核心结论（必须记住）：

输出语句的位置	在 DAG 上得到的序列
进入递归前输出（标准 DFS）	DFS 序列
退出递归前输出（本题修改）	逆拓扑序

为什么"退出递归时输出"得到逆拓扑序？

考虑 DAG 中的任意一条有向边 （含义： 必须在 之前完成）。在递归 DFS 中，从 出发会先递归遍历它的所有可达后继（包括 ），然后才退出 的递归——也就是说：

一定先于 退出递归。

把"退出递归"作为输出时机，意味着 一定先于 输出。换言之，对每条边 ，输出顺序里 在 前面——这恰好是拓扑序的反向，即逆拓扑序。

举个最小例子：DAG 仅 3 个顶点 。

从 调用递归：

1. 进入 的递归 → 进入 的递归 → 进入 的递归
2. 没有后继，退出 （输出 ）
3. 的所有后继处理完，退出 （输出 ）
4. 的所有后继处理完，退出 （输出 ）

输出序列：。拓扑序应为 ，所以 正是它的逆序——即逆拓扑序。

为什么必须是 DAG？ 题目特意强调"有向无环图"。如果有环，DFS 会因访问标记跳过环上某些节点，输出的不是任何拓扑序的反序——题目排除了这种情况。

最终答案是 B（逆拓扑有序序列）。

记忆口诀："进栈拓扑、出栈逆拓扑"。基于 DFS 的拓扑排序算法实际上就是用"出栈输出"得到逆拓扑序，再把序列反转一下作为最终结果。