题目

若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是()

错因

A

误以为 BFS 必须从 a 开始（"图的第一个节点"），看到 h 起点就直接判错。但题目没规定起点——任意顶点都可以作为 BFS 起点。从 h 出发：先访 h，h 的邻居 {a, c}（顺序 c 先 a 后），逐层展开完全合法。

B

同理，误以为不能从 e 起点；或者觉得 b、h、c、d 在末尾的顺序"很乱"。其实从 e 起，e 邻居 {a, f, g}，第二层从 a 拓展出 b、h，再后从 b 拓展出 c、d，全程符合 BFS 分层原则。

C

误判 d 起点不合法。从 d 起，邻居 {b, c}，再依次展开 a、h，最后拿到 e 之后才到 f、g，逐层推进无破绽。其实最容易识别 BFS 合法性的方法是：看每个节点的所有未访问邻居是否都在它之后、它的"邻居的邻居"之前出现——C 完全满足。

总解析

邻接表（从图中读出）：

顶点	邻居
a	b, e, h
b	a, c, d
c	b, d, h
d	b, c
e	a, f, g
f	e
g	e
h	a, c

BFS 合法性的核心约束：

设访问序列为 ，则 的所有未访问邻居都必须在 中早于" 邻居的邻居"出现。
等价表述：BFS 严格按"层序"展开——源点的邻居必须先全部访问完，才能开始访问邻居的邻居。

逐项验证：

A：h, c, a, b, d, e, g, f ✓

从 h 出发：访 h → 队列 {a, c}（按邻居顺序入队）。
取 c → 访 c → c 的新邻居 {b, d}（h 已访）→ 队列 {a, b, d}。
取 a → 访 a → a 的新邻居 {b（已在队）, e, h（已访）} → 实际入队 {e}，队列 {b, d, e}。
依次取 b、d → 无新邻居 → 取 e → 访 e → e 的新邻居 {g, f}（顺序自由）→ 末尾 g, f。

B：e, a, f, g, b, h, c, d ✓

从 e：访 e → 队列 {a, f, g}。取 a → a 新邻居 {b, h}，入队 {f, g, b, h}。取 f、g → 无新；取 b → b 新邻居 {c, d}，入队 {h, c, d}。取 h → 无新；取 c、d。

C：d, b, c, a, h, e, f, g ✓

从 d：队列 {b, c}。取 b → 新邻居 {a}，入队 {c, a}。取 c → 新邻居 {h}，入队 {a, h}。取 a → 新邻居 {e}，入队 {h, e}。取 h → 无新；取 e → 新邻居 {f, g}。

D：a, b, c, d, h, e, f, g ✗ 不合法

从 a：访 a → a 的邻居是 {b, e, h}，无论入队顺序如何，b、e、h 三个节点必须先全部出现，才能轮到它们的邻居（c、d、f、g）。

但 D 序列是 a, b, c, d, h, e, f, g——c 和 d（b 的邻居）在 e、h（a 的邻居）之前就被访问了，违反了"先访问完源点的所有邻居" 这一硬规则。

直觉对照：从 a 出发的合法 BFS 第二层只能是 {b, e, h} 的某个排列，第三层才轮到 {c, d, f, g}。D 把"a 的邻居 e、h"延后到 c、d 之后，等于用了 DFS 的思路——沿着 b → c、d 一路深挖，这是 DFS 不是 BFS。

最终答案是 D。