GESP 八级 · GESP 八级样题（C++ 组） 第 24 题

下面是图的深度遍历的代码，则横线处可以填入：if(vis[x]) return。 

这题考的是图遍历中visited数组防死循环的核心作用。拿到题先想：递归DFS会反复访问同一点，横线处填什么能立刻切断回路？

学生容易纠结visited标记时机，误以为必须先赋值再判断，或者认为条件判断本身多余。其实只要检查已访问状态就能阻断，赋值是后续步骤。还有人会把isVisited误读为“判断是否可访问”，忘了它本质是防重复。

【考点】递归与搜索｜图遍历｜visited标记防死循环

1. 考纲定位：GESP八级"递归与搜索"模块核心。命题人专挖"只背模板不懂原理"的考生——他们机械调用DFS，却说不清为什么必须加visited。八级要求理解递归终止条件，visited正是防重复访问、死循环的关键。

2. 解题心法：看到DFS代码，先想"已访问标记的作用"。DFS是递归，同一连通块里会多次遇到同一个点，不标记就会无限递归。题目横线处在递归入口，填if(vis[x]) return;正好在再次遇到已访问点时立即返回，避免重复处理。所以答案是A。

3. 陷阱拆解：错误选项B对应"填if(vis[x]) return;是错的"。命题人利用的是"visited应该在递归后标记"的误区——实际上标记时机不影响正确性，只要在递归前检查即可。还有人会纠结"要不要先vis[x]=true再判断"，但本题只问条件本身，无需赋值。B选项看似更严谨，实则只是把检查提前了，不影响正确性。

4. 反命题思维：如果把条件改成"填if(vis[x]=true) return;是否正确？"，答案就变成B，因为赋值和返回顺序错了。刷到类似题时，先问自己："这个visited判断是放在递归前还是后？是检查还是赋值？"——这就是命题人想考的细节。这样改条件，横线处若填if(vis[x]=true) return;则逻辑错误，应改为vis[x]=true; if(vis[x]) return;或类似。

【考频趋势】图遍历相关考点在图形结构模块累计213题，其中GESP八级占73题，近年呈爆发式增长：2023年32题、2024年61题、2025年56题、2026年40题，说明命题人越来越重视图算法细节。visited标记作为图遍历的"防死循环"核心，必是高频考点。

【预测】基于2024-2026年图形结构题量激增且八级占比高，未来GESP八级仍会持续考查图遍历细节，如visited标记时机、递归终止条件、连通块计数等。暂无足够依据预测具体题型变化，但"防死循环"类陷阱题大概率延续。