GESP 八级 · GESP 202509 C++ 八级 第 7 题

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

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

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

【考点】图论遍历｜BFS 复杂度｜邻接表存储

1. 🎯 考纲定位（考点定位）

GESP 八级图论与网络模块，BFS 是必考算法。命题人卡住考生对遍历算法复杂度与存储结构关系的模糊记忆，多数人选错 O(V) 或 O(E)。