NOIP 提高组初赛 · NOIP 2013 提高组初赛试题 第 18 题

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

这题考DFS遍历顺序对终点的影响。别被‘最后一个’吓到，其实只要顺着图从A0出发，选哪条路先走就决定了谁最后被碰见。先想清楚A0能连谁，再按邻接表顺序（或字母序）一步步往下钻，遇到死胡同就回溯。最后剩下的那个没被访问过的点，就是答案。

很多同学把DFS和BFS搞混，以为会一层层扫完，其实DFS是一条道走到黑再回头。还有个坑是以为‘下标大的点’一定后访问，其实完全取决于你从A0出发时，先挑哪个邻居往下走。如果A0先连了A1，那A1这条分支可能就把A3或A4都提前访问了；反之若A0先连A3，那A4反而可能压轴。

考点与概念

这道题考查的是图的深度优先搜索（DFS）遍历顺序。

DFS是什么人话版：想象你站在A0门口，手里拿着一张单行道地图。你只能往一个方向一直走，直到走到没路（死胡同）或者已经去过（黑掉），这时候你才退回来（回溯），接着去下一个没走过的路口。整个过程就像“一条道走到黑，黑了再回头”。

命题人怎么挖坑： 1. 顺序陷阱：题目说“遍历顺序与顶点字母下标无关”，意思是你不能默认A0先连A1再连A2……你得看图的边。但很多考生会下意识按字母序（A0→A1→A2…）去走，结果掉进坑里。 2. 终点误解：问“最后一个遍历到的顶点”，其实不是问“最远的点”，而是问“在DFS过程中，最后被访问到的那个点”。这取决于你从A0出发时，先选哪条边往下钻。

思考心法：拿到题先想什么？

1. 从A0出发，它有哪些邻居？ 看图，A0连了A1、A2、A3、A4中的几个（具体看原图，A0→A1、A0→A2、A0→A3、A0→A4都有边）。所以A0可以任选其中一个作为“第一条路”。 2. 选哪条路先走？ DFS是贪心往下钻。如果你先选A0→A1，那接下来会一直沿着A1的未访问邻居往下走，直到A1这条分支走完（比如A1→A2→A3→A4都走一遍），这时候A1分支全黑了，才回溯到A0，再去走A0→A2、A0→A3…… 3. 回溯时谁最后被碰见？ 关键看“最后一条被完整走完的分支”的末端是谁。