CSP-J 入门级 · CSP 2021 入门级第一轮 第 14 题

以 $a$ 为起点，对下边的无向图进行深度优先遍历，则 $b,c,d,e$ 四个点中有可能作为最后一个遍历到的点的个数为（ ）。 

从a出发，DFS会一直往深处走直到无路可走才回溯。关键不是看谁离a最远，而是看谁在‘最深处’且没有未访问的邻居。只要调整邻接表的顺序，就能让不同点成为最后一个被访问的。

很多学生看到图就下意识认为‘最后一个访问的肯定是离起点最远的点’，比如d或e，这是把BFS的层序思想套用到DFS上了。其实DFS是‘一条路走到黑’，如果某条路能一直通到某个叶子，那这个叶子就会是最后一个；但如果邻接表里先选了另一条路，那条路的尽头就会变成最后一个。所以不能只盯着距离，要看连通分支里‘最深’且‘无后续分支’的点。

考点定位：这道题考的是深度优先搜索（DFS）在连通图上的遍历特性，核心在于理解“最后一个被访问的点”是如何产生的。它不是简单的距离问题，而是路径选择与回溯的结果。

概念拆解：DFS的规则很死板——从起点出发，沿着邻接表里的顺序，走到一个没访问过的邻居就立刻跳过去，继续往下走；只有当当前点的所有邻居都被访问过（或无路可走）时，才会回溯到上一个点。因此，最后一个被访问的点，一定是某条路径的终点，且在该终点处没有未被访问的邻居。

命题人怎么挖坑：题目没给邻接表顺序，只问“有可能”。这意味着只要存在一种合法的邻接顺序，让某个点成为最后一个，那这个点就符合条件。很多学生会误以为只有离a最远的点（比如d或e）才可能是最后一个，忽略了b和c也可能在特定顺序下成为“最深”的点。

思考路径： 1. 从a出发，邻接顺序不同，第一跳可以是b或e。 2. 若先走a→b→c→d→e，e是最后一个；若先走a→e→d→c→b，b是最后一个。 3. 关键是看每个点在“最深路径”中的位置： - d和e：无论怎么走，它们总会被先访问，因为从a出发，迟早会经过它们，而它们后面还能走到别的点（d能到c/e，e能到a/d），所以它们不可能是最后一个。 - b和c：如果邻接顺序让DFS优先走a→e→d→c→b，那么b就是最后一个；如果走a→b→c→d→e，c就是最后一个。这两个点都可能在“最深处”且没有未访问邻居。 4. 因此，b和c都有可能成为最后一个，d和e不可能。

避坑提醒：别把BFS的“层序最远”和DFS的“路径最深”混为一谈。DFS的最后一个点取决于你“先选哪条路”，而不是“谁离起点远”。

考频与趋势：图的基本概念题库共281题，DFS单独考过61题，其中CSP入门级仅4题，但2021年考了1题，2024年DFS考到13题，2025年9题，2026年22题，呈现明显上升趋势，尤其是入门级和GESP七级八级高频出现。这类“给定起点、问最后一个点”的变体题在2024-2026年几乎成了常客，命题人喜欢在邻接顺序上做文章，让学生判断“可能”的情况。

预测：基于2024-2026年DFS题量激增且题型偏向“可能性判断”的趋势，未来入门级和GESP七级八级仍会高频出现类似题目，可能会把图结构稍微复杂化（比如增加节点或改变连通性），但核心逻辑不变——只要存在一种邻接顺序使某点成为最后一个，该点就入选。暂无足够依据预测具体年份或更细的变体形式，但方向明确：继续考“DFS遍历顺序的不确定性”。