GESP 六级 · GESP 202309 C++ 六级 第 24 题

如果节点数为 $N$，广度搜索算法的最差时间复杂度为 $O(N)$。

别急着背结论，先想BFS到底干了啥：进队一次，出队后扫一遍邻接表。总操作数=点数+边数。题里说'最差O(N)'，关键就看边数会不会让复杂度飙升。

最容易掉进两个坑：一是死记'BFS是O(N)'，没意识到那是针对稀疏图的特例，遇到稠密图就慌；二是把'最差'理解成绝对上限，以为无论图多稠密都是O(N)，其实最坏情况是O(N+M)。命题人就是卡住这个惯性，让你误以为只数节点就够了，忘了边数可能远多于节点。

【考点】图算法｜BFS遍历｜时间复杂度分析

这道题考查的是广度优先搜索（BFS）在一般图上的时间复杂度，核心在于理解BFS的遍历过程与图的规模（点数N、边数M）的关系。

拿到题先想BFS流程：从起点入队，然后循环：取出队首u，遍历u的每个邻接点v，若v未被访问则入队。伪代码里，"while队列非空"保证了每个点只会被取出一次（进队一次），所以点的处理代价是O(N)；"对u的每个邻接点v执行操作"意味着每条边只会被检查一次（从u到v），所以边的处理代价是O(M)。因此，BFS的总时间复杂度严格来说是O(N+M)。

命题人的视角很清晰：六级图算法模块常默认图是稀疏的，即边数M与点数N同阶（M≈N），在这种前提下O(N+M)等价于O(N)。题中特意用"最差"二字，其实是想卡住那些只背结论的学生——如果图是稠密的（比如完全图，M≈N²），那BFS确实会退化成O(N²)，但六级考纲通常不要求处理这种极端稠密情况，而是考察对稀疏图默认设定的理解。所以"最差O(N)"在六级语境下是成立的。

思考心法：看到BFS别只数节点，要数"进队次数"和"检查边次数"。进队次数=点数，检查边次数=边数。只有当M和N同阶时，才能说O(N)。如果命题人改成"任意图BFS都是O(N)"，那答案就错了；改成"DFS最差复杂度"，因为DFS也是O(N+M)，答案仍为A。

避坑提醒：很多学生看到"最差"就紧张，以为要往O(N²)想，或者反过来觉得O(N)是绝对上限。其实"最差"在这里是相对稀疏图而言的。只背结论、不理解本质，就会在这类陷阱题上栽跟头。记住：BFS的复杂度永远由点数加边数决定，稀疏图里边数不多，所以O(N)没问题；稠密图里边数爆炸，O(N)就不成立了。