GESP 七级 · GESP 202509 C++ 七级 第 8 题

对一个包含 $ V $ 个顶点、$ E $ 条边的图，执行广度优先搜索，其最优时间复杂度是（ ）。

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

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

【考点】BFS｜时间复杂度｜邻接表

考纲定位：图论算法与复杂度分析，GESP 七级核心考点。命题人专卡那些会背 BFS 流程但不懂复杂度分析的考生——很多人误以为只要遍历顶点就是 O(V)，完全忽略了边的处理开销。

解题思维：BFS 的核心是队列遍历：每个顶点进队出队各一次，共 O(V)；每条边被检查一次（邻接表存边时），共 O(E)。因此总复杂度 O(V + E)。这是图遍历的通用公式，记住它就能秒杀同类题。

陷阱拆解：选项 D 的 O(V²)是命题人埋的雷——对应邻接矩阵表示，但题目问的是"最优"复杂度，暗示用邻接表。选项 C 的 O(E)太绝对，没考虑孤立点；选项 B 的 O(V)更是典型思维定势。如果你只背"BFS 快"而不理解数据结构的代价，就会掉进这个陷阱。

反命题思维：若改成"邻接矩阵下的 BFS 复杂度"，答案就是 O(V²)；若问"稠密图 BFS"，答案仍为 O(V²)。刷到类似题时，先问自己"图怎么存？"——这才是命题人想让你思考的。