GESP 七级 · GESP 202412 C++ 七级 第 15 题

下列选项中，哪个不可能是下图的深度优先遍历序列（ ）。


DFS 使用栈（或递归），沿一条路径走到底再回溯，适合遍历所有可能状态。注意回溯时的状态恢复。

DFS 递归遍历时注意状态回溯（恢复现场）。图遍历需要visited数组避免重复访问和死循环。

【考点】DFS遍历｜图的邻接表表示｜遍历合法性判定

考纲定位：本题出自GESP七级"图与树"模块，专门考察DFS遍历序列的合法性。命题人把这道题放在试卷里，就是卡住那些只背"先访问再回溯"口诀、却不懂无向图中邻居访问时机和回溯路径的学生——他们往往把回溯当成"随便访问"，导致选项A这种明显违反DFS规则的答案被误选。

解题思维：判断一个序列是否可能是DFS结果，核心是模拟过程。从起点1出发，按邻接顺序访问未访问邻居；回溯时继续访问其他分支。关键观察：若序列中某节点u后面出现了v，而v是u的邻居且v未在u之前被访问，则访问u时v必须未被访问，否则v应在u之前被访问。因此，DFS序列中，对于每个节点u，其后继节点必须是u的邻居且未访问过，或者是回溯时访问的其他分支节点。

陷阱拆解：选项A（1,2,3,5,7,8,6,9,4）看似合理，实则致命：4是1的直接邻居，但4出现在序列末尾，说明在访问1时4未被访问，后来回溯到1的其他邻居时4被访问。根据DFS规则，如果4是1的邻居且在访问1时4未被访问，那么4应该在1之后尽早访问，而不是在序列末尾。更关键的是，如果图的结构使得4是1的唯一邻居，那么访问1后必须访问4，而不是访问其他节点。因此A违反DFS规则。

反命题思维：如果把图改成有向图，DFS序列会不同；或者改变邻接表顺序，序列会变。提醒学生：刷到类似题时，先问自己"命题人想考我什么"——这里考的是DFS回溯时的节点访问顺序，以及无向图中邻居的访问时机。