GESP 八级 · GESP 八级样题（C++ 组） 第 8 题

下面程序使用 BFS 遍历一个有 $n$ 个顶点、边权都为 $1$ 的无向图 $G$，下面说法正确的是（ ）。 

拿到 BFS 题先盯住两个变量：tl 是每层循环的计数器，dis 只在入队时赋值且按层递增，这样就能直接排除干扰项。

很多同学会把 tl 当成全局遍历计数，其实它每层清零只统计当前层节点数；还有人把层序赋值误读成贪心策略，混淆 BFS 与 Dijkstra；若默认邻接矩阵就会误判复杂度为 O(n²)，但图论题默认用邻接表，复杂度应为 O(n+m)。

考点定位

GESP八级图论模块核心考点，专治对BFS距离数组本质的混淆——把“访问顺序”当成“贪心策略”，把“层控变量”当成“总计数”。

解题思维

BFS在单位权无向图上天然求最短路径。关键观察：dis数组只在入队时赋值，且赋值顺序严格遵循层序——第一层全赋1，第二层全赋2……tl变量的作用是控制每层出队节点数，不是记录总遍历数。所以C正确（st到其他点的最短距离），A错（tl是层计数），B错（距离变化是单调递增而非贪心），D错（邻接表BFS是O(n+m)）。