BFS 中的队列（Queue）：深入解析其功能与作用
在 BFS（广度优先搜索）中，queue（队列）扮演着核心角色，它控制着 节点的访问顺序 ，确保搜索按 层级顺序 进行。队列的 FIFO（先进先出） 特性，保证了 BFS 适用于 最短路径搜索 、连通性检查 、拓扑排序 等场景。
🔍 Queue 在 BFS 代码中的应用
在 BFS 代码中，我们通常使用 queue 进行以下操作：
ini
复制代码
java
复制编辑
public List
List
Set
Deque
queue.offer(start);
while(!queue.isEmpty()){
GraphNode curNode = queue.poll();
if(visited.contains(curNode)){
continue;
}
result.add(curNode);
visited.add(curNode);
for(GraphNode nei: curNode.neighbors){
queue.offer(nei);
}
}
return result;
}
👀 关键点
queue.offer(start); 初始化：将起点放入队列，准备开始搜索。
curNode = queue.poll(); 取出队首元素 进行处理，保证按照 FIFO 访问顺序。
queue.offer(nei); 将当前节点的所有邻居入队，确保逐层遍历。
🔄 Queue 中元素的功能解析
在 BFS 过程中，queue 中存储的 每个元素 都有其特定的功能，我们可以从多个角度进行解析。
1️⃣ 作为「待访问节点」
队列存储的是即将访问的节点，即「当前层的邻居 + 下一层的起点」。
保证广度优先，确保每一层的节点都被访问完后，才进入下一层。
示例：
ini
复制代码
mathematica
复制编辑
图结构：
A
/ \
B C
/ \
D E
BFS 过程：
1. queue = [A] （初始）
2. queue = [B, C] （访问 A，加入 B 和 C）
3. queue = [C, D, E] （访问 B，加入 D 和 E）
4. queue = [D, E] （访问 C）
5. queue = [E] （访问 D）
6. queue = [] （访问 E）
2️⃣ 作为「层级标记」
queue 通过 FIFO 规则 让同一层的节点按照顺序访问，确保每一层处理完后，才进入下一层。
适用于 层次遍历（如二叉树层次遍历、最短路径）。
示例：求二叉树的最大深度
arduino
复制代码
java
复制编辑
while (!queue.isEmpty()) {
int size = queue.size(); // 记录当前层的元素数量
for (int i = 0; i < size; i++) {
TreeNode cur = queue.poll();
if (cur.left != null) queue.offer(cur.left);
if (cur.right != null) queue.offer(cur.right);
}
depth++; // 进入下一层
}
3️⃣ 作为「最短路径搜索工具」
BFS 在 无权图中 计算最短路径时，队列中每个元素都代表「路径中下一步的节点」。
例如，在迷宫问题或最短单词接龙问题中，queue 维护 当前路径的前进方向。
示例：最短路径问题（单源最短路径）
scss
复制代码
java
复制编辑
while (!queue.isEmpty()) {
GraphNode curNode = queue.poll();
for (GraphNode nei : curNode.neighbors) {
if (!visited.contains(nei)) {
distance.put(nei, distance.get(curNode) + 1); // 计算最短路径
queue.offer(nei);
}
}
}
4️⃣ 作为「拓扑排序的辅助结构」
在 拓扑排序 （Topological Sorting）中，queue 主要存储 入度为 0 的节点，用于逐步移除依赖关系。
例如，在 课程表问题（Course Schedule） 里，队列负责维护当前可以选的课程。
示例：拓扑排序（Kahn's Algorithm）
ini
复制代码
java
复制编辑
Queue
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.offer(i); // 入度为 0 的课程入队
}
}
while (!queue.isEmpty()) {
int course = queue.poll();
for (int neighbor : graph.get(course)) {
inDegree[neighbor]--;
if (inDegree[neighbor] == 0) {
queue.offer(neighbor);
}
}
}
✅ 总结
🎯 Queue 的核心作用
角度
功能
存储待访问节点
记录当前搜索范围，保证 FIFO 顺序
层级标记
维护 BFS 的逐层扩展特性
最短路径搜索
计算无权图的最短路径
拓扑排序
记录入度为 0 的节点，控制依赖关系
💡 关键优化
提前标记 visited，避免重复入队：
ini
复制代码
java
复制编辑
visited.add(start);
queue.offer(start);
使用双向 BFS 优化搜索复杂度（适用于 word ladder 等问题）。
采用 ArrayDeque 代替 LinkedList 提高性能（避免链表额外的存储开销）。
🚀 结论
queue 是 BFS 的核心数据结构 ，确保搜索 层级顺序 进行。
不同场景下，queue 中的元素代表不同意义（如待访问节点、最短路径扩展、拓扑排序辅助）。
合理优化 queue 使用 （如提前标记 visited、双向 BFS）能显著提升算法效率。
📌 下一步学习方向
研究 双向 BFS 的优化（减少搜索层数）。
练习 基于 BFS 的实际问题 （如 word ladder、滑动谜题）。
结合 优先队列（PriorityQueue） 研究 Dijkstra 算法。
💡 希望这篇文章能帮助大家更深入理解 queue 在 BFS 中的应用！