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

从顶点 $v_1$ 开始遍历下图 $G$ 得到顶点访问序列，在下面所给的 4 个序列中符合广度优先的序列有几个？（ ）

$\{v_1\ v_2\ v_3\ v_4\ v_5\}$，$\{v_1\ v_2\ v_4\ v_3\ v_5\}$，$\{v_1\ v_4\ v_2\ v_3\ v_5\}$，$\{v_1\ v_2\ v_4\ v_5\ v_3\}$


这题考的是 BFS 的核心机制：队列出队顺序决定访问顺序。拿到题别急着背层序，先画出 v1 的邻居按什么顺序入队，再顺着队列推一遍。同层节点顺序必须跟邻接表一致，这是判断合法性的唯一标准。

最容易栽跟头的是以为 BFS 结果只有一种，或者把树的层序遍历直接套用到图上。其实图上邻居入队顺序不固定时，同层节点排列可以不同。另一个坑是忽略距离严格递增这个硬性条件，导致把第三层节点提前放第二层。

【考点】广度优先搜索（BFS）｜队列操作｜图的遍历顺序

1. 考纲定位

GESP 七级「图论」模块，专卡「BFS 顺序不唯一」这个盲区。命题人把「默认邻接顺序就是输入顺序」的误区植入，让只会背「BFS=层序」的考生全挂。