GESP 六级 · GESP202609 C++ 六级 第 21 题

若使用下列代码从节点 start 开始访问一棵树，则第一次到达某个节点时所经过的边数，一定是从 start 到该节点的最少边数。

vector<int> tree[100];
bool visited[100];
int dist[100];
void search(int start) {
queue<int> q;
q.push(start);
visited[start] = true;
dist[start] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : tree[u]) {
if (!visited[v]) {
visited[v] = true;
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
}

看到题先想 BFS 的层序遍历特性。队列 FIFO 保证同一层节点先出队，新节点入队时距离已是最小。

选项 B 陷阱在于混淆 BFS 与 DFS。有人误以为"先访问"不等于"最短"，其实无权图中 BFS 首次访问即最短。

考纲定位

GESP 六级图论模块，考察 BFS 在树（无权图）上的最短路径性质。命题人卡住的是考生对"层序遍历"与"最短路径"关系的理解——这是图论基础中最容易被忽视的定理之一。

解题思维

BFS 队列 FIFO 保证同一层节点先出队，新节点入队时距离已是最小。首次访问即最短。