蓝桥杯 Java B 组 之队列的应用（BFS 入门）
Day 2：队列的应用（BFS 入门）
一、什么是队列（Queue）？
队列（Queue）是一种 先进先出（FIFO, First In First Out） 的数据结构，类似于排队买票，先来的人先买到票，后来的排在队尾。队列的两个基本操作：
- 入队（enqueue）：元素添加到队列尾部。
- 出队（dequeue）：元素从队列头部移除。
核心操作：
offer(e)：元素入队（队尾）。
poll()：出队（队首）。
peek()：查看队首元素（不出队）。
isEmpty()：判断队列是否为空。
在 Java 中，Queue 主要可以使用 LinkedList 或 ArrayDeque 来实现：
import java.util.LinkedList;
import java.util.Queue;
public class QueueExample {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(1); // 入队
queue.offer(2);
queue.offer(3);
System.out.println(queue.poll()); // 出队，输出 1
System.out.println(queue.peek()); // 查看队首元素，输出 2
}
}
二、广度优先搜索（BFS, Breadth-First Search）
1. 什么是 BFS？
广度优先搜索（BFS）是一种用于 图遍历 和 最短路径搜索 的算法。它的工作方式类似于 逐层扩展，先访问起点的所有邻居，再访问邻居的邻居，依次进行。
BFS 适用于： ✅ 求解最短路径（迷宫、最短跳数）
✅ 求解连通性问题（岛屿问题、社交网络关系）
✅ 状态搜索（八数码问题、滑动拼图）
2. BFS 的基本原理
- 使用队列（Queue）
- 从起点开始，将其加入队列
- 不断从队列中取出节点，并扩展其邻居
- 直到找到目标，或者遍历完整个图
三、练习：迷宫最短路径（固定地图）
1. 题目描述
给定一个 n × m 的迷宫，1 表示墙壁，0 表示可以走的路径，找到从起点 (0,0) 到终点 (n-1,m-1) 的最短路径长度（走一步算一步）。
示例输入（固定地图）：
5 5
0 0 1 0 0
1 0 1 0 1
1 0 0 0 1
1 1 1 0 1
0 0 0 0 0
输出（最短步数）：
9
规则
- 只能上下左右走（不能走对角线）
- 不能穿墙（1 是墙，0 是可走路径）
- 求最短路径（步数最少）
2. BFS 解法
BFS 适用于这种 最短路径问题，因为它按层遍历，保证先找到的路径就是最短的。
关键点
- 使用队列存储当前可以到达的点
- 使用 visited 数组避免走回头路
- 用 方向数组 处理上下左右移动
- BFS 逐层扩展，保证最短路径
3. BFS 代码实现
import java.util.*;
class MazeSolver {
// 方向数组（上、下、左、右移动）
private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public static int shortestPath(int[][] maze) {
int n = maze.length, m = maze[0].length;
Queue<int[]> queue = new LinkedList<>();
boolean[][] visited = new boolean[n][m];
// 起点加入队列
queue.offer(new int[]{0, 0, 1}); // (x, y, 步数)
visited[0][0] = true;
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int x = cell[0], y = cell[1], step = cell[2];
// 到达终点
if (x == n - 1 && y == m - 1) {
return step;
}
// 处理四个方向的移动
for (int[] dir : DIRECTIONS) {
int newX = x + dir[0], newY = y + dir[1];
// 判断新位置是否越界，并且是可行的路径
if (newX >= 0 && newX < n && newY >= 0 && newY < m && maze[newX][newY] == 0 && !visited[newX][newY]) {
queue.offer(new int[]{newX, newY, step + 1});
visited[newX][newY] = true; // 标记已访问
}
}
}
return -1; // 无法到达终点
}
public static void main(String[] args) {
int[][] maze = {
{0, 0, 1, 0, 0},
{1, 0, 1, 0, 1},
{1, 0, 0, 0, 1},
{1, 1, 1, 0, 1},
{0, 0, 0, 0, 0}
};
int result = shortestPath(maze);
System.out.println("最短路径步数: " + result);
}
}
四、代码详解
- Queue<int[]> 存储 (x, y, step)，表示当前位置 (x, y) 以及到达这里的步数。
- visited[][] 数组 用于标记哪些点已经走过，防止重复遍历。
- DIRECTIONS[][] 方向数组 让我们方便地向上、下、左、右移动。
- BFS 遍历过程
- 从 (0,0) 出发，加入队列
- 从队列中取出 (x, y)，尝试向四个方向走
- 如果到达终点 (n-1,m-1)，返回步数
- 如果能走，则加入队列，标记为已访问
- 直到队列为空，若未找到路径，返回 -1
五、复杂度分析
- 时间复杂度：O(n*m)，每个点最多访问一次。
- 空间复杂度：O(n*m)，用于存储 visited[][] 和 Queue。
六、常见错误与优化
| 错误点 | 错误描述 | 修正方式 |
| 未标记访问 | 可能会多次访问同一个点，导致超时 | 使用 visited[][] 数组，确保每个点只访问一次 |
| BFS 方向错误 | 只考虑单向移动，无法找到正确路径 | 使用 方向数组 {上, 下, 左, 右} |
| 队列操作错误 | 误用 stack.pop() 而非 queue.poll() | BFS 需要使用队列 (Queue)，而非栈 (Stack) |
| 无法到达终点 | 遇到死路时无法返回 -1 | 在 while 结束后检查是否到达终点 |
七、蓝桥杯常考点总结
| 考点 | 典型题目 | 优化技巧 |
| BFS 基础 | 最短路径、岛屿数量 | 使用 visited[][] 避免重复访问 |
| 迷宫问题 | 固定地图、随机地图 | 方向数组 {上, 下, 左, 右} 处理移动 |
| 状态搜索 | 八数码问题、最短翻转 | 记录状态避免重复搜索 |
知识点总结
队列的特性：先进先出（FIFO），适用于需要按顺序处理元素的场景。
队列的基本操作：入队（Enqueue）和出队（Dequeue）。
广度优先搜索（BFS）：一种用于遍历或搜索树或图的算法，使用队列来实现，能够保证找到的路径是最短路径。
BFS 解决迷宫最短路径问题的步骤：初始化队列、标记起点为已访问、不断取出队列头部节点并扩展相邻节点，直到找到终点或队列为空。
六、蓝桥杯常考点
队列的基本操作和应用：可能要求选手使用队列实现一些简单的算法，如 BFS。
广度优先搜索（BFS）：是蓝桥杯的常考算法之一，常出现在图论、迷宫等问题中，考查选手对 BFS 思想和队列操作的理解。
最短路径问题：如迷宫最短路径、图的最短路径等，要求选手能够使用 BFS 或其他算法解决。
七、蓝桥杯易错点
队列操作错误：在使用队列时，要注意入队和出队的顺序，避免出现逻辑错误。
节点访问标记问题：在 BFS 中，要正确标记节点是否被访问过，避免重复访问导致死循环或结果错误。
边界条件处理：在检查节点是否合法时，要考虑边界条件，如节点是否在地图范围内，避免数组越界错误。
方向数组设置错误：在扩展相邻节点时，方向数组的设置要正确，确保能够覆盖所有可能的方向。