GESP 八级 · GESP 202506 C++ 八级 第 24 题

有 $V$ 个顶点、$E$ 条边的图的深度优先搜索遍历时间复杂度为 $O(V + E)$。

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】深度优先搜索｜图遍历复杂度

1. 考纲定位 GESP 八级算法与数据结构模块，DFS 遍历复杂度是必考基础概念。命题人专门考这个，就是为了筛掉那些背结论不背推导过程的考生。

2. 解题思维 DFS 用栈（或递归）实现，每个顶点进栈恰好一次，O(V)；对每个顶点，遍历其所有邻接边，每条边被访问一次（或两次，无向图），总计 O(E)。故总复杂度 O(V+E)。通法：任何基于邻接表实现的图遍历（BFS/DFS）都是 O(V+E)，因为访问顶点和访问边是互斥且覆盖的。

3. 陷阱拆解 选 B 的人通常掉进两个坑：一是把 DFS 当成 O(V²)（误用邻接矩阵视角），二是把"遍历"理解成"只走一遍"，忘了还要处理每个顶点的出边。题目没给图的具体表示，按算法通例默认邻接表，因此 A 才是标准答案。

4. 反命题思维 若改成"邻接矩阵表示的 DFS 时间复杂度为 O(V+E)"，答案就翻成 B；若改成"DFS 在最坏情况下访问所有顶点"，答案还是 A。刷到这类题先问自己：图表示是什么？遍历覆盖的是顶点还是边？