6.3.1 广度优先遍历

BFS 用队列按距离层推进。起点发现时立即标记并入队；每次出队 u，未访问邻居 v 立即标记、记录 parent/dist 后入队。非连通图需对每个尚未访问顶点重新启动，形成 BFS 森林。

手工状态

边 0-1,0-2,1-3,2-3，按编号邻接。队列[0]；处理0后[1,2]；处理1发现3后[2,3]；处理2时3已标记；输出0,1,2,3，dist为0,1,1,2。

结构与代码

seen[s]=1;q.push(s);while(!q.empty()){u=q.front();q.pop();for(v:g[u])if(!seen[v]){seen[v]=1;dist[v]=dist[u]+1;q.push(v);}}

正确性依据

无权图中队列按非降距离出队，首次发现 v 的路径比任何尚未处理候选都短，因此 dist 是最少边数。邻接表复杂度 O(V+E)。

错解反馈

出队才标记导致重复入队；用栈变DFS；加权图直接用BFS求权值最短路。

迁移训练

网格每步代价1，如何求最少步？答案把格子作顶点做BFS，入队时标记并记录前驱。