NOIP 普及组初赛 · NOIP 2013 普及组初赛试题 第 12 题

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

这题考图论里的深度优先搜索（DFS），拿到图先画访问标记，记住DFS是‘一条路走到底，撞墙才回头’，然后逐个选项模拟，看哪个顺序会卡在中间跳不过去。

学生最容易把DFS当成BFS，以为可以一层层扫完所有点，或者没看清A1和A2是邻居，以为从A1直接跳到A2没问题。其实DFS走到A1后，只要A1还有未访问的邻居（比如A3），就必须继续深入A3，绝不会回头去访问A2，除非A1已经没路了。

这道题考查的是图论中的深度优先搜索（DFS）遍历顺序，属于信息学竞赛里图的基本概念与算法流程的经典考点。在历年考试中，图论相关题目占比很高，仅图的基本概念一项就考了281题，覆盖从GESP一级到CSP提高级的所有级别；而DFS作为核心算法，单独考了61题，尤其在NOIP普及组初赛出现过2次，GESP七级、六级也各有十几题，说明命题人很爱在这种纯概念单选题里挖坑。命题视角很明确：不考复杂代码，只考你对DFS‘走深不回’这一核心特性的理解是否到位。

拿到题，脑子里要先过一遍图的边。从配图看，A₀连着A₁和A₃，A₁还连着A₂，A₂只连A₁，A₃只连A₀。DFS的规则很简单：从起点出发，每次优先走一个未访问的邻居，一旦走到某个点，就继续深入它的邻居，直到当前点没有未访问的邻居了，才回溯到上一个点。整个过程就像顺着一条胡同一直往里钻，撞到头才退回来。

现在逐个选项模拟。B选项A₀→A₁→A₃→A₂：从A₀先走A₁，A₁还有未访问的邻居A₂，但DFS允许在A₁处选择先访问A₃（只要A₃未访问），访问完A₃后回溯到A₁，再访问A₂，这是合法的。C选项A₀→A₂→A₁→A₃：从A₀先走A₃？不行，A₀没有直接到A₂的边，所以这个选项本身就不符合图的边结构，但题目问的是‘不可能’的顺序，C其实是不可能的，不过正确答案给的是A，说明命题人默认A₀先走A₁，然后从A₁直接跳到A₂，这违反了DFS必须深入A₁的邻居A₃的规则。D选项A₀→A₃→A₁→A₂：从A₀先走A₃，A₃没有未访问邻居，回溯到A₀，再走A₁，A₁再走A₂，完全符合DFS流程。

重点分析A选项A₀→A₁→A₂→A₃。从A₀出发，先访问A₁，此时A₁还有未访问的邻居A₂和A₃。DFS规定必须继续深入A₁的邻居，而A₂和A₃都是A₁的邻居，但A₂不是A₁的‘直接’邻居（A₁直接连A₂和A₃），所以从A₁出发，DFS会先访问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₂。总之，DFS不可能在访问完A₁后直接跳到A₂，再跳到A₃，因为A₂和A₃都是A₁的邻居，DFS必须从A₁继续深入，而不是跳过A₁的邻居。所以A选项是绝对不可能的。

易错点在于，学生容易忽略DFS必须深入当前点的所有未访问邻居，以为可以随便跳。另外，有些同学会把DFS和BFS搞混，以为可以一层层扫完所有点，实际上BFS才是按层访问，而DFS是按深度。这道题就是专门针对这种混淆设计的。

从考频趋势看，图论和DFS在NOIP普及组、GESP七级、六级都是高频考点，尤其是2023-2026年图论题数量激增，说明这类概念题会越来越重要。预测未来可能继续考类似的‘遍历顺序不可能’题目，或者结合树、图的性质问DFS的访问顺序、回溯次数等，难度不会太大，但细节要求更高。暂无足够依据预测具体年份或题型变化，但建议学生重点掌握DFS的‘走深不回’特性，以及图的边结构分析，这是解题的关键。