一、文章定位
这篇文章主要讲解算法竞赛中非常常见的一类模型：
在无权图、网格图、状态图中，求从起点到终点的最短步数。
这里的“最短路”不是 Dijkstra 那种带权最短路，而是 每一步代价相同 的最短路问题。
典型场景包括：
迷宫最短路径
棋盘最少步数
单词变化最少次数
数字状态最少操作次数
多个起点同时扩散
地图中距离最近目标的问题
这类问题的核心算法就是 BFS，广度优先搜索。
二、什么是 BFS？
1. BFS 的基本思想
BFS，全称 Breadth-First Search，中文叫 广度优先搜索。
它的搜索顺序可以理解为：
从起点出发，先搜索距离为 1 的所有点，再搜索距离为 2 的所有点，再搜索距离为 3 的所有点……
也就是说，BFS 是一层一层向外扩展的。
例如从起点 S 出发：
第 0 层：S
第 1 层：S 一步可以到达的点
第 2 层：从第 1 层继续走一步可以到达的点
第 3 层：从第 2 层继续走一步可以到达的点
...所以当 BFS 第一次到达某个点时，一定是用最少步数到达的。
这就是 BFS 能求最短路的根本原因。
三、BFS 为什么可以求最短路？
1. 适用前提
BFS 求最短路有一个非常重要的前提：
每条边的权值相同，通常都可以看作 1。
比如：
在迷宫里，每走一格花费 1 步；
在棋盘上，每移动一次花费 1 步；
在状态转移中，每进行一次操作花费 1 次；
在普通无权图中，每经过一条边花费 1。
如果边权不同，就不能直接使用普通 BFS，需要考虑 Dijkstra、Bellman-Ford、SPFA、0-1 BFS 等算法。
2. BFS 的层次性
BFS 使用队列维护搜索顺序。
队列的特点是：
先进先出。
这保证了先进入队列的点会先被扩展。
假设起点距离是 0，那么：
起点扩展出的点距离是 1；
距离为 1 的点扩展出的点距离是 2；
距离为 2 的点扩展出的点距离是 3；
所以 BFS 的搜索过程天然按照距离递增的顺序进行。
因此：
当一个点第一次被访问时，当前得到的距离就是它的最短距离。
四、BFS 最短路模型的基本写法
BFS 的核心通常包括四个部分：
1. 定义队列
2. 初始化起点
3. 不断取出队首元素
4. 枚举下一步可以到达的状态伪代码如下：
m其中 dist[x] 表示：
从起点走到状态
x的最短距离。
五、网格图中的 BFS
网格图 BFS 是算法竞赛中最常见的 BFS 模型。
例如给定一个 n × m 的迷宫：
S表示起点；T表示终点；.表示可以走；#表示障碍物。
每次可以向上下左右四个方向移动一格，问从 S 到 T 的最少步数。
1. 方向数组
在网格 BFS 中，通常用方向数组简化代码：
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};表示四个方向：
上：(-1, 0)
下：(1, 0)
左：(0, -1)
右：(0, 1)如果题目允许八个方向移动，可以写成：
static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};2. 网格 BFS 模板
import java.util.*;
public class Main {
static int n, m;
static char[][] grid;
static int[][] dist;
static boolean[][] visited;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static class Node {
int x;
int y;
Node(int x, int y) {
this.x = x;
this.y = y;
}
}
static int bfs(int sx, int sy, int tx, int ty) {
Queue<Node> queue = new LinkedList<>();
queue.offer(new Node(sx, sy));
visited[sx][sy] = true;
dist[sx][sy] = 0;
while (!queue.isEmpty()) {
Node cur = queue.poll();
int x = cur.x;
int y = cur.y;
if (x == tx && y == ty) {
return dist[x][y];
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
continue;
}
if (visited[nx][ny]) {
continue;
}
if (grid[nx][ny] == '#') {
continue;
}
visited[nx][ny] = true;
dist[nx][ny] = dist[x][y] + 1;
queue.offer(new Node(nx, ny));
}
}
return -1;
}
}3. 代码细节解释
起点入队
queue.offer(new Node(sx, sy));
visited[sx][sy] = true;
dist[sx][sy] = 0;这三句是 BFS 初始化的核心。
含义是：
起点加入队列；
起点已经被访问；
起点到自己的距离为 0。
从队列中取出当前点
Node cur = queue.poll();
int x = cur.x;
int y = cur.y;BFS 每次从队首取出一个点，然后扩展它的相邻点。
枚举四个方向
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
}这里的 (nx, ny) 表示下一步要走到的位置。
判断是否合法
if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
continue;
}
if (visited[nx][ny]) {
continue;
}
if (grid[nx][ny] == '#') {
continue;
}一般需要判断三件事：
是否越界；
是否已经访问过；
是否是障碍物。
只有合法位置才能加入队列。
更新最短距离
dist[nx][ny] = dist[x][y] + 1;因为每走一步代价都是 1，所以新位置的距离等于当前位置距离加 1。
六、普通图中的 BFS
除了网格图，BFS 也可以用于普通无权图。
例如有 n 个点，m 条边，求从点 1 到点 n 的最短距离。
1. 邻接表存图
static List<Integer>[] graph;如果有一条无向边 a - b：
graph[a].add(b);
graph[b].add(a);如果是有向边 a -> b：
graph[a].add(b);2. 普通图 BFS 模板
import java.util.*;
public class Main {
static int n, m;
static List<Integer>[] graph;
static int[] dist;
static boolean[] visited;
static int bfs(int start, int target) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
visited[start] = true;
dist[start] = 0;
while (!queue.isEmpty()) {
int u = queue.poll();
if (u == target) {
return dist[u];
}
for (int v : graph[u]) {
if (visited[v]) {
continue;
}
visited[v] = true;
dist[v] = dist[u] + 1;
queue.offer(v);
}
}
return -1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
graph = new ArrayList[n + 1];
dist = new int[n + 1];
visited = new boolean[n + 1];
for (int i = 1; i <= n; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
// 无向图
graph[a].add(b);
graph[b].add(a);
// 如果是有向图，只保留：
// graph[a].add(b);
}
int answer = bfs(1, n);
System.out.println(answer);
}
}七、BFS 的时间复杂度
1. 网格图 BFS
对于一个 n × m 的网格，每个格子最多入队一次。
所以时间复杂度是：O(n × m)
空间复杂度也是：O(n × m)
因为需要 vis 数组、dist 数组和队列。
2. 普通图 BFS
对于普通图，每个点最多访问一次，每条边最多检查一次。
所以时间复杂度是：O(n + m)
其中：
n是点数；m是边数。
空间复杂度是：O(n + m)
主要来自邻接表、队列、访问数组和距离数组。
八、BFS 的常见变形
1. 多源 BFS
普通 BFS 只有一个起点。
多源 BFS 有多个起点。
做法是：
一开始把所有起点同时加入队列，并且它们的距离都设为 0。
例如：
求每个空地到最近水源的距离；
求每个房间到最近门的距离；
求地图上每个点到最近怪物的距离；
腐烂橘子问题。
模板如下：
import java.util.*;
public class Main {
static int n, m;
static int[][] dist;
static char[][] grid;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static class Node {
int x;
int y;
Node(int x, int y) {
this.x = x;
this.y = y;
}
}
static void multiSourceBfs(List<Node> sources) {
Queue<Node> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
Arrays.fill(dist[i], -1);
}
for (Node source : sources) {
queue.offer(source);
dist[source.x][source.y] = 0;
}
while (!queue.isEmpty()) {
Node cur = queue.poll();
int x = cur.x;
int y = cur.y;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
continue;
}
if (grid[nx][ny] == '#') {
continue;
}
if (dist[nx][ny] != -1) {
continue;
}
dist[nx][ny] = dist[x][y] + 1;
queue.offer(new Node(nx, ny));
}
}
}
}多源 BFS 的本质是：
多个起点同时向外扩散，谁先到达某个点，谁就是该点的最近来源。
2. 状态 BFS
有些题目不是在图上走，而是在“状态”之间转移。
例如：
从数字
1变到数字n；每次可以
+1、-1、×2；问最少操作次数。
这时每一个数字就是一个状态，每一次操作就是一条边。
例如：
import java.util.*;
public class Main {
static int bfs(int start, int target) {
int MAX = 100000;
int[] dist = new int[MAX + 1];
Arrays.fill(dist, -1);
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
dist[start] = 0;
while (!queue.isEmpty()) {
int x = queue.poll();
if (x == target) {
return dist[x];
}
int[] nexts = {x - 1, x + 1, x * 2};
for (int nx : nexts) {
if (nx < 0 || nx > MAX) {
continue;
}
if (dist[nx] != -1) {
continue;
}
dist[nx] = dist[x] + 1;
queue.offer(nx);
}
}
return -1;
}
public static void main(String[] args) {
int start = 5;
int target = 17;
System.out.println(bfs(start, target));
}
}这类题目的关键是：
把问题抽象成状态图。
只要每次操作的代价都是 1，就可以用 BFS 求最少操作次数。
3. 记录路径的 BFS
如果题目不仅要求最短距离，还要求输出路径，可以使用 pre 数组记录前驱。
例如普通图中，从 start 到 target 输出一条最短路径。
import java.util.*;
public class Main {
static int n, m;
static List<Integer>[] graph;
static int[] dist;
static int[] pre;
static boolean bfs(int start, int target) {
Queue<Integer> queue = new LinkedList<>();
Arrays.fill(dist, -1);
Arrays.fill(pre, -1);
queue.offer(start);
dist[start] = 0;
while (!queue.isEmpty()) {
int u = queue.poll();
if (u == target) {
return true;
}
for (int v : graph[u]) {
if (dist[v] != -1) {
continue;
}
dist[v] = dist[u] + 1;
pre[v] = u;
queue.offer(v);
}
}
return false;
}
static List<Integer> getPath(int start, int target) {
List<Integer> path = new ArrayList<>();
int cur = target;
while (cur != -1) {
path.add(cur);
if (cur == start) {
break;
}
cur = pre[cur];
}
Collections.reverse(path);
if (path.get(0) != start) {
return new ArrayList<>();
}
return path;
}
}使用方式：
if (bfs(start, target)) {
List<Integer> path = getPath(start, target);
System.out.println("最短距离：" + dist[target]);
System.out.println("最短路径：" + path);
} else {
System.out.println("无法到达");
}九、BFS 常用 Java 写法总结
1. 队列定义
Queue<Integer> queue = new LinkedList<>();或者：
Queue<Node> queue = new LinkedList<>();2. 入队
queue.offer(x);3. 出队
int cur = queue.poll();4. 判断队列是否为空
while (!queue.isEmpty()) {
// BFS
}5. 初始化距离数组
一维数组：
Arrays.fill(dist, -1);二维数组：
for (int i = 0; i < n; i++) {
Arrays.fill(dist[i], -1);
}十、BFS 与 DFS 的区别
BFS 和 DFS 都是搜索算法，但它们适用的场景不同。
一句话总结：
求无权图最短路，优先想到 BFS；求遍历、连通性、枚举方案，可以考虑 DFS。
十一、BFS 最短路模型的做题步骤
遇到一道题时，可以按照下面的思路分析：
1. 判断是否适合 BFS
看题目是否满足：
每次操作的代价是否相同？
是否要求最少步数、最短距离、最少操作次数？
状态数量是否可以接受？如果答案是肯定的，大概率可以使用 BFS。
2. 定义状态
状态可能是：
一个点：u
一个坐标：(x, y)
一个数字：num
一个字符串：str
一个棋盘局面：board
多个变量组成的状态：(x, y, key, step)BFS 中最重要的一步就是定义状态。
例如：
迷宫问题：状态是当前位置
(x, y)；钥匙迷宫问题：状态是
(x, y, keyState)；数字变换问题：状态是当前数字
x；八数码问题：状态是当前棋盘排列。
3. 定义转移
转移就是从当前状态可以走到哪些下一个状态。
例如：
网格图：上下左右移动
数字问题：+1、-1、×2
字符串问题：替换一个字符
棋盘问题：交换空格和相邻位置4. 判断合法性
每个新状态都要判断：
是否越界？
是否满足题目限制？
是否已经访问过？
是否是障碍？
是否超过最大范围？5. 更新距离并入队
dist[next] = dist[cur] + 1;
q.push(next);如果第一次到达终点，可以直接返回答案。
十二、BFS 常见错误
1. 入队时没有立刻标记访问
错误写法：
q.push(next);然后等出队时再标记访问。
这样可能导致同一个点被重复加入队列，严重时会超时。
推荐写法：
vis[next] = true;
q.push(next);也就是：
一旦入队，就立刻标记访问。
2. 没有初始化 dist 数组
如果使用 dist 判断是否访问过，建议初始化为 -1：
memset(dist, -1, sizeof dist);然后：
dist[start] = 0;判断是否访问过：
if (dist[next] != -1) continue;这样可以不用单独开 vis 数组。
3. 坐标越界
网格 BFS 最容易写错的是越界判断。
标准写法：
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;如果题目下标从 1 开始，则写成：
if (nx < 1 || nx > n || ny < 1 || ny > m) continue;4. 忘记障碍物判断
迷宫类问题中，障碍物不能走：
if (g[nx][ny] == '#') continue;不同题目障碍符号可能不同，比如：
# 墙
* 障碍
X 障碍
1 不可走需要根据题目调整。
5. 状态没有设计完整
有些题不能只用 (x, y) 表示状态。
例如钥匙迷宫中，同一个位置在不同钥匙状态下是不同状态：
(x, y, keyState)如果只记录 (x, y) 是否访问过，就可能错误剪枝。
例如：
第一次到达某个门前时没有钥匙；
第二次带着钥匙到达同一个位置时，实际上可以继续前进。这种情况必须把钥匙状态也加入 BFS 状态。
十三、推荐例题
十四、文章总结
BFS 是算法竞赛中解决无权最短路问题的核心算法。
它的关键特点是：
一层一层向外扩展。它适合解决：
最少步数、最短距离、最少操作次数、最近目标、多源扩散。BFS 的基本框架是：
队列 + 访问标记 + 距离数组 + 状态转移。做 BFS 题时，最重要的是想清楚三件事：
1. 状态是什么？
2. 如何从当前状态转移到下一个状态？
3. 如何判断一个状态是否合法？只要这三个问题想清楚，BFS 最短路模型的大部分题目都可以顺利解决。
搜索算法中的最短路模型：BFS
本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
评论交流
欢迎留下你的想法