NOIP 提高 2013 第一轮 第 18 题：以 A_0 作为起点，对下面的无向图进行深度优先遍历时（遍历的顺序与顶点字母的下

题目

以 $A_0$ 作为起点，对下面的无向图进行深度优先遍历时（遍历的顺序与顶点字母的下标无关），最后一个遍历到的顶点可能是（   ）。

答案

C、D

题解

考点定位

本题考「DFS 最后访问点（不定项）」,对应大纲 4.3.3 搜索（难度【4】）。

解题过程

DFS 序的末点：从 A₀ 出发某条完整探索路径的终点 = 沿途「走到底」的最远点。按原图（A₀—A₁—A₂—A₃—A₄ 链 + 附加边）枚举各起点分支的末端：可达末端为 A₃、A₄（A₁、A₂ 在所有分支中都会先于其邻接未访点被越过……依官方答案）。

答案：C、D。

易错提醒

① DFS 末点必是某条极简路径的末端（其所有邻点都已访问）；② 逐分支模拟「每次走编号最小/最大邻点」两极情形。