NOIP 普及 2013 第一轮 第 12 题：判断不可能的深度优先遍历顺序

题目

以 $A_0$ 作为起点，对下面的无向图进行深度优先遍历时，遍历顺序不可能是（	）。

选项

• A. $A_0, A_1, A_2, A_3$
• B. $A_0, A_1, A_3, A_2$
• C. $A_0, A_2, A_1, A_3$
• D. $A_0, A_3, A_1, A_2$

答案

A

题解

考点定位

深度优先遍历与回溯。

解题过程

图中的边为 A₀—A₁、A₀—A₂、A₀—A₃、A₁—A₃。两条斜线的交叉处没有结点。

若从 A₀ 先访问 A₁，A₁ 还有未访问的邻点 A₃，必须先递归访问 A₃，之后才能回到 A₀ 去访问 A₂。因此顺序 A₀,A₁,A₂,A₃ 不可能。

其余顺序都可以实现：

• A₀,A₁,A₃,A₂：访问 A₃ 后回溯到 A₀，再访问 A₂。
• A₀,A₂,A₁,A₃：A₂ 是叶子，回到 A₀ 后再访问 A₁、A₃。
• A₀,A₃,A₁,A₂：先沿 A₃、A₁ 访问，再回到 A₀ 访问 A₂。

选 A。

易错提醒

遍历序列只记录首次访问的结点，不记录回溯，因此相邻两项不一定直接有边。