GESP 七级 · GESP202609 C++ 七级 第 7 题

在无权图中，使用 BFS 从起点开始遍历，并在访问由结点 u 扩展的相邻结点 v 时记录 dist[v] = dist[u] + 1 ，且起点的 dist 为 0 ，则最终 dist[v] 表示的是（　　）。

无权图BFS按层遍历，队列中节点按距离起点递增顺序出队。每扩展一层，dist值加1，因此dist[v]必然等于起点到v的最少边数。通法：无权图最短路径用BFS，有权图用Dijkstra。

B选项度数与遍历无关；C选项无权图边权均为1，不存在"最大边权"概念；D选项连通块大小指节点数而非距离。最阴险陷阱是命题人故意用"无权图"限定，若学生误以为BFS在有权图中也适用，就会选错。

1. 考纲定位

本题考查《GESP 考试大纲》图论模块的广度优先搜索算法。命题人放这道题，卡住的是大量学生混淆"无权图BFS"与"有权图Dijkstra"的边界——他们知道BFS能求最短路径，但说不清为什么。

2. 解题思维

看到题先想：BFS按层遍历，队列中节点按距离起点递增顺序出队。关键观察：每扩展一层，dist值加1。数值推演：起点dist=0，其邻居dist=1，邻居的邻居dist=2，依此类推。通法：无权图最短路径用BFS，有权图用Dijkstra。