GESP 六级 · GESP 202412 C++ 六级 第 23 题

宽度优先搜索算法（BFS）保证了每个节点在最短路径的情况下被访问。

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

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

【考点】广度优先搜索｜最短路径

1. 🎯 考纲定位：GESP 六级图论模块必考 BFS 性质，命题人用此题卡住混淆 BFS 与 DFS 的考生，测试对无向图最短路径保证的理解。本知识点位于六级"图与搜索"章节，是算法基础中的核心考点，多数考生会误以为"遍历即最短"，实则只有 BFS 满足。

2. 🧠 解题思维：BFS 按层遍历，同一层节点距离相同，下一层距离 +1；因此每个节点首次被访问时即对应最短路径，结论必然为真。关键观察在于队列的 FIFO 特性，保证距离递增，无需额外判断，直接可得答案。

3. 🪤 陷阱拆解：错误选项 B 源于将"任意遍历"与"最短路径"强绑，命题人利用"绝对化表述"诱导考生忽略 BFS 的层级特性；若误以为 DFS 也能保证最短路径，就会掉进这个陷阱。命题人还设置了"未说明图是否有权值"的模糊点，但 BFS 默认用于无权图，此处属于对默认条件的考察。

4. 🔄 反命题思维：若改为"在加权图中 BFS 保证最短路径"则答案为假，命题人想让你先区分有无权值——遇到类似题先问"图是否有权值？"，就能快速定位考点。再改 DFS 为"深度优先搜索保证最短路径"则必错，这提醒我们 BFS 与 DFS 的本质差异在于层级与路径长度。