GESP 七级 · GESP 202606 C++ 七级 第 10 题

无向图的边为 $(1,2)$、$(1,3)$、$(2,4)$、$(3,4)$、$(4,5)$。从顶点 $1$ 开始进行 BFS，每轮根据出队顶点，将与其相邻顶点按编号从小到大入队，则顶点 $4$ 第一次入队时，队列的状态为（ ）。

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

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

【考点】BFS 遍历｜队列结构｜邻居排序

1. 考纲定位 本题考查的是 GESP 七级《算法与数据结构》模块中 BFS 搜索 的核心考点。命题人设置这道题，就是卡住大多数考生对 队列状态动态变化 的追踪能力——很多人只背了 BFS 的伪代码，却忘了队列里到底还剩谁，这题就是专门挖这个坑的。

2. 解题思维 按 BFS 流程严格模拟：初始队列 [1]。弹出 1，向邻居 2,3 入队 → 队列 [2,3]。弹出 2，邻居 4 尚未入队 → 队列 [3,4]。此时 4 首次入队，队列状态定格为 [3,4]。这类题的通法是 严格按队列顺序模拟，不要跳步，每一步都要问自己"队列里现在有哪些元素"。

3. 陷阱拆解 选项 A 错在把 1 和 2 都留在队列里（弹出即消失）；选项 B 错在误以为 2 还在队列里（其实 2 弹出时 4 才入队）；选项 D 错在把 5 提前入队（5 是 4 弹出时入队的）。最阴险的陷阱是 把"入队顺序"和"弹出顺序"混为一谈——命题人故意用"第一次入队"这个词，就是看你有没有意识到 4 入队时 2 已经出队了。

4. 反命题思维 反命题视角：如果把题目改成"顶点 4 第一次弹出时队列状态"，答案就会变成 [5]；如果改成"从顶点 2 开始 BFS"，队列状态会完全不同。刷到这类题，先问自己："当前这一步，队列里到底留下了谁？"