GESP 七级 · GESP 202312 C++ 七级 第 14 题

给定一个简单有向图 $G$，判断其中是否存在环路的下列说法哪个最准确？（ ）

别急着套公式，先想：有向图判环到底在干什么？是找‘访问中’的节点还是看能不能排拓扑序？两者本质都是遍历全图，复杂度同阶，谁快纯属玄学。

学生最容易掉进两个坑：一是死记‘DFS 找环’，看到有向图就下意识选 DFS，忽略了 BFS 配合入度队列（拓扑排序思想）同样能线性时间判环；二是把‘时间复杂度同阶 O(V+E)'偷换概念成‘实际运行速度一样’，没考虑到常数因子、栈溢出风险、队列开销等工程细节。题目问‘最准确’，恰恰就是考你对这些细微差别的敏感度。

【考点】有向图环检测｜BFS/DFS 时间复杂度｜拓扑排序

考纲定位：本题对应 GESP 七级图论模块中“图遍历与环检测”综合考点。命题人把 BFS、DFS、拓扑排序揉进一个选择题，卡住的是学生只会背“DFS 找环”结论，却不懂两者时间复杂度本质同阶。

解题思维：检测有向图环的本质是遍历所有顶点与边。DFS 通过递归栈标记“访问中”节点，BFS 则用入度队列做拓扑排序，两者均需访问每条边一次、每个点一次，时间复杂度均为 O(V+E)。既然阶数相同，说“谁更快”就是无意义的比较——除非题目给出具体图数据，否则无法判断。

陷阱拆解：A、B 分别诱导“迭代比递归快”或“递归更直接”的直觉，但忽略栈溢出风险与队列开销；C 看似正确，却把“理论阶数相同”偷换为“实际速度相同”——一旦图规模大、深度深，DFS 栈帧开销可能远超 BFS 的队列操作。最阴险的是题干“哪个最准确”：若只背结论，会选 C；若理解本质，必选 D。

反命题思维：若改成“无向图环检测”，BFS/DFS 仍同阶；若改成“判断是否存在环且要求输出环”，DFS 显然更优。刷到类似题先问：命题人想考我“复杂度阶数”还是“常数因子”？七级图论题大多考前者，D 正是对“过度推断”的终极测试。

考频趋势：从题库数据看，图的基本概念在 GESP 七级共考过 85 题，占比极高；BFS 在七级考了 12 题，DFS 考了 20 题，说明两者都是高频考点，但单独对比速度的题目极少。拓扑排序在七级仅 0 题，却在 NOIP 提高组初赛考了 3 题，提示高阶考试更爱考拓扑思想。

预测：基于现有数据，未来七级仍大概率考“遍历与环检测”的基础概念辨析，不会突然转向常数因子优化。若出现新题型，更可能是结合拓扑排序思想（如入度为 0 的节点处理）来考 BFS 判环，而非单纯比 DFS/BFS 速度。暂无足够依据预测具体年份考题，但“理论同阶，实际难定”这一考点大概率持续存在。