GESP 七级 · GESP 202409 C++ 七级 第 15 题

下列选项中，哪个可能是下图的广度优先遍历序列（ ）。


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

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

【考点】广度优先搜索｜遍历顺序的结构性约束｜队列操作的正确性

---

1. 考纲定位 GESP 七级考查图遍历算法，BFS 属于图论基础。命题人放这道题，是卡住考生"只背 BFS 定义，不验证结构"的弱点——很多人会凭直觉排个序就选，却从不回溯原图。

---

2. 解题思维 看到题先想 BFS 的队列机制——根节点入队，每次出队后把未访问邻居按邻接表顺序入队，出队顺序就是遍历序列。关键观察：原图无向，根为 1。按 A 模拟：1 入队 → 出队 1，邻居 3,5,7,4,2,6,8,9 依次入队；再依次出队得到 1,3,5,7,4,2,6,8,9 与 A 完全吻合。

---

3. 陷阱拆解 B 项以 9 开头，违反 BFS 根固定为 1 的常识，命题人用"换根"制造迷惑；C 项把 6,8,9 提前，说明出题人故意把同一层的节点打乱考察"层序"；D 项 9,4,7 开头，不仅根错了，还把 4,7 提前到第二层，暴露考生对"先入先出"队列机制的盲区。

---

4. 反命题思维 命题人若把图改成有向、增加回边、或让某层节点数翻倍，A 的合法性就会动摇；若把根换成 3，B 就可能成为新题。刷到类似题时先问自己："这个序列是否真的对应 BFS 的出队顺序，而不是我凭直觉排的？"