GESP 七级 · GESP 七级样题（C++ 组） 第 12 题

下面有向图中的数字表示顶点序号，则从 1 号顶点出发的 BFS 遍历的输出顶点序列可能是（ ）。 

这题考广度优先搜索（BFS）的队列顺序。拿到图先别急着看编号，要盯着起点1的邻居是谁、谁先出现。记住BFS核心：队列里谁先进谁就先出，同层节点顺序完全由邻接表顺序决定。

学生最容易掉进两个坑：一是把BFS当成排序，默认按顶点编号从小到大输出，结果选了D（1 2 4 3）；二是没看清图中1的邻居顺序，以为2在3前面，其实图里3连在2前面，导致入队顺序反了。还有少数人会误以为4是1的邻居，选了A或B，这是没读懂拓扑结构。

【考点】广度优先搜索（BFS）｜队列FIFO特性｜邻接表顺序对遍历结果的影响

1. 概念与命题视角

BFS的本质是用队列按层遍历图：先访问起点，然后把起点的邻居按图中出现的顺序依次入队；之后队首元素出队，再把它未访问的邻居入队。命题人最爱挖的坑就是把编号大小和入队顺序混淆，或者故意画反邻居顺序来测试你是否真的在按图走。