GESP 七级 · GESP 202406 C++ 七级 第 10 题

图的存储和遍历算法，下面说法错误的是（ ）。

DFS 使用栈（或递归），沿一条路径走到底再回溯，适合遍历所有可能状态。注意回溯时的状态恢复。

DFS 递归遍历时注意状态回溯（恢复现场）。图遍历需要visited数组避免重复访问和死循环。

【考点】图的遍历｜递归｜栈

🎯 考纲定位 GESP 七级大纲"图论与网络"章节，命题人卡住的是考生对"遍历逻辑"与"数据结构"关系的混淆——以为 DFS 和先序遍历本质不同，实则它们遵循同一套访问顺序。

🧠 解题思维 先看选项 B，立刻想到 DFS 递归版：visit(u); for v in adj(u): dfs(v);。再想二叉树先序：visit(root); preorder(root.left); preorder(root.right);。对比两者：都是"当前节点先访问，然后依次访问子节点"。逻辑完全一致，差异仅在于"子节点"的定义（图的邻接点 vs. 树的左右子树）。因此 B 说"道理不一样"是错的。其他选项 A/C/D 都是教材级结论，无需纠结。

🪤 陷阱拆解

• 选项 B 利用"图有环、树无环"的刻板印象，诱导考生认为 DFS 和先序遍历必然不同，实则环不影响遍历顺序逻辑。
• 选项 C 看似绝对，但 DFS 确实需要栈（递归隐式栈），命题人用"需要借助栈"来强调显式栈实现，属于标准表述。
• 选项 D 的"正好是"是邻接表定义的核心，命题人用数学符号 $v_i$ 增加严谨感，实则考查是否理解度 = 邻接链表长度。

🔄 反命题思维 若把"二叉树先序"换成"后序"，B 就变对了；若把"DFS"换成"BFS"，B 也变对了——命题人故意用"道理不一样"这个模糊表述，让只背结论的考生掉进语义陷阱。刷到类似题时，先问自己：在比较什么？逻辑还是数据结构？