GESP 七级 · GESP 202406 C++ 七级 第 22 题

非连通图不能使用广度优先搜索算法进行遍历。

BFS 使用队列，按层次逐层遍历，适合求最短路径（边权为1时）。核心：标记已访问，避免重复入队。

BFS 入队后立即标记已访问，防止重复入队。队列为空时搜索结束。注意区分树的BFS（无需visited标记）和图的BFS。

【考点】广度优先搜索｜图遍历｜连通性判断

【考纲定位】GESP 七级算法与数据结构模块中图论部分。命题人想卡住"认为 BFS 只能用于连通图"的普遍误解，很多考生看到"非连通图"就默认无法遍历，却忽略了 BFS 本质是逐点启动的组件遍历算法。

【解题思维】看到"非连通图+BFS"先回忆 BFS 定义：从起点出发遍历所有可达点。关键观察——非连通图中存在多个连通分量，BFS 仅能覆盖起点所在分量。推理链：非连通图→存在未访问点→BFS 单次运行无法覆盖所有点→必须对每个未访问点再启动一次 BFS。通法：处理任意图时，若不确定是否遍历完，先标记所有点，对每个点若未标记就启动一次 BFS，直到所有点都被访问。

【陷阱拆解】选项 B 为错误，命题人用"不能使用"这种绝对化表述制造认知陷阱。学生容易把"单次 BFS 无法遍历全图"等同于"BFS 算法本身不能用于非连通图"，这是偷换概念。最阴险的细节在于"不能使用"没有说明"需要多次使用"，而很多教材示例图都是连通的，强化了单一运行印象。如果你只背结论"BFS 用于连通图"，就会掉进这个绝对化表述的坑里。

【反命题思维】命题人视角：如果把"非连通图"改成"连通图"，答案变成 A；如果改成"非连通图必须多次 BFS 才能遍历"，答案变成 A。刷到图遍历题时，先问自己"命题人是不是在考我是否考虑了所有连通分量？"