题目

下列选项中，不是下图深度优先搜索序列的是( )。

错因

A

可能漏看了 这条出边，以为 只能去 或 ，于是觉得序列开头""不合法。其实 有三条出边（指向 ），邻接表把 排在最前面，DFS 第一步就走 。后续 、 无出边回溯到 、 也无未访问出边再回溯到 、最后从 访问 ——每一步都合法。

B

可能误以为 DFS 必须按字母（编号）小的邻居优先，认为 第一步必须是 ，""开头就违法。但 DFS 算法对邻居顺序不强制——同一张图，不同的邻接表存储顺序会得到不同序列，都属于合法 DFS。 每步沿真实出边走，序列合法。

C

可能卡在""这步觉得跳得太远——中间隔着 、、 三层回溯，怀疑 DFS 不允许"跨这么多层"。但 DFS 的回溯深度不限： 无出边回溯到 ， 仅有的出边 已走过再回溯到 ， 也已走过继续回溯到 ，此时 还有 未访问就访问 。每一步回溯都符合"当前顶点无未访问出边"的条件，序列合法。

总解析

先把图的出边整理出来：

顶点	出边目标
	（无）

DFS 判断准则：

• 关键规则：当访问到顶点 、且 还有未访问的出边邻居时，下一步必须深入 的某个未访问邻居（不能回溯）。只有 所有出边邻居都访问过了，才允许回溯到上一层。
• 邻居之间的选择顺序由邻接表决定，任何顺序都合法。
• 回溯可以连续多层——只要每层都满足"无未访问出边"条件。

逐项验证：

• A（V1, V5, V4, V3, V2）：（回溯到 ， 唯一出边 已走，再回溯到 ）。✓
• B（V1, V3, V2, V5, V4）：。每步都沿真实出边，最后 无出边，回溯收工。✓
• C（V1, V2, V5, V4, V3）：（连续回溯 ）。✓
• D（V1, V2, V3, V4, V5）： 后，问题来了—— 的出边邻居是 ，且 此时未访问。按 DFS 规则，必须从 深入 ，不能"跳回 再访问 "。所以序列第三个不可能是 ，只可能是 。✗

反推 D 不合法的核心：DFS 不允许"还有未走完的支路就先回溯"。 之间没有出边，要从 走到 ，必须经过回溯到 ，但回溯的前提是 已无未访问出边邻居，而 还在等着——条件不满足。

最终答案是 D。