NOIP 提高 2012 第一轮 第 12 题：该题选项在原卷 OCR 中缺失，待人工复核。

题目

从顶点 $A_0$ 出发，对有向图（	）进行广度优先搜索（BFS）时，一种可能的遍历顺序是 $A_0,A_1,A_2,A_3,A_4$。

答案

A、D

题解

考点定位

本题考「BFS 遍历序（不定项）」,对应大纲 4.3.3 搜索（难度【3】）。

解题过程

BFS 从 A₀ 出发按「入队顺序访问邻接点」。序列 A₀,A₁,A₂,A₃,A₄ 表示 A₀ 与其余四点都相邻（第一层全出）。依图：图 1（星形 A₀ 连全部）✓；图 4（A₀ 连全部+其余成链）✓；图 2/3 的 A₀ 邻接不全 ✗。

答案：A、D。

易错提醒

① BFS 序首个之后必是起点的全部邻居；② 逐图核对 A₀ 的邻接表覆盖 A₁..A₄。