CSP-J 2021 第一轮 第 14 题：DFS最后遍历到的点可能是哪些

题目

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

选项

• A. 1
• B. 2
• C. 3
• D. 4

答案

B

题解

答案是 B．2，最后一个遍历到的点可能是 \(b\) 或 \(e\)。

DFS（深度优先遍历）的规则是：当前点还有未访问的邻点，就继续往下走；没有了，才回退。“遍历到”指第一次访问这个点。

从 \(a\) 出发，所有可能的访问顺序如下：

注意：表中的箭头表示首次访问的顺序，省略了回退过程。例如第三种情况，到达 \(e\) 后要先退回 \(c\)，才能继续访问 \(d\)。

所以共有 2 个点可能最后被访问。