3.3.4 队列应用：广度优先与层次推进

队列适合保存“已经发现、等待处理”的对象。图的广度优先搜索从起点入队并立即标记；每次取出队头，枚举未访问邻居，标记后入队。立即标记而不是出队时才标记，可避免同一结点被多个前驱重复入队。

queue<int> q; seen[s]=true; q.push(s);
while(!q.empty()){
 int u=q.front(); q.pop();
 for(int v:g[u]) if(!seen[v]){seen[v]=true; q.push(v);}
}

在无权图中，第一次发现结点时经过的边数最少，因此 BFS 可求最短路径。维护 dist[v]=dist[u]+1 和 parent[v]=u，即可恢复距离与路径。时间为 $O(V+E)$，空间 $O(V)$。

手工推演：边为 A-B,A-C,B-D,C-D，邻接按字母序。队列先 [A]；处理 A 后 [B,C]；处理 B 发现 D 后 [C,D]；处理 C 时 D 已标记不重复入队；最后处理 D。D 的最短距离为 2。

树的层序遍历同理。若要分层，可在每轮先记录当前队列长度，这个长度就是本层结点数；处理完这些结点后，队列里恰好是下一层。

错解反馈：邻居入队但不标记会重复；用栈替换队列会变成深度优先，不能保证无权最短路；把 BFS 用于带负权或一般加权最短路，适用条件不成立。

迁移题：网格中每步上下左右且每步代价 1，如何求最少步数？答案把可走格视为无权图结点做 BFS，入队时记录距离并标记。独立验收：能逐轮列队列、访问集合和距离数组。