BFS 算法框架
一句话总结
BFS 算法的本质是二叉树的层序遍历扩展到图结构，通过队列实现按层级扩散搜索，适合求解最短路径问题。
核心要点
1. BFS 与树/图遍历的关系
- DFS/回溯 的本质是二叉树的递归遍历（前中后序）
- BFS 的本质是二叉树的层序遍历扩展到图结构
- 从基础数据结构到高级算法的推导路径：
- 二叉树遍历 → 多叉树遍历 → 图遍历（加 visited 数组）→ BFS 算法
- BFS 适合最短路径问题，因为它按层扩散，第一次到达目标时步数最少
2. BFS 通用框架（三种写法）
第一种写法（简单但局限大）：
// 从 start 开始 BFS，寻找 target
void bfs(Node start, Node target) {
Queue<Node> q = new LinkedList<>();
HashSet<Node> visited = new HashSet<>();
q.offer(start);
visited.add(start);
while (!q.isEmpty()) {
Node cur = q.poll();
if (cur == target) {
// 找到目标
return;
}
for (Node neighbor : cur.neighbors()) {
if (!visited.contains(neighbor)) {
q.offer(neighbor);
visited.add(neighbor);
}
}
}
}
第二种写法（最常用，中等难度题）：
// 从 s 开始 BFS 遍历图的所有节点，且记录遍历的步数
// 当走到目标节点 target 时，返回步数
int bfs(int s, int target) {
boolean[] visited = new boolean[graph.size()];
Queue<Integer> q = new LinkedList<>();
q.offer(s);
visited[s] = true;
// 记录从 s 开始走到当前节点的步数
int step = 0;
while (!q.isEmpty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
int cur = q.poll();
// 判断是否到达终点
if (cur == target) {
return step;
}
// 将邻居节点加入队列，向四周扩散搜索
for (int to : neighborsOf(cur)) {
if (!visited[to]) {
q.offer(to);
visited[to] = true;
}
}
}
step++;
}
// 如果走到这里，说明在图中没有找到目标节点
return -1;
}
第三种写法（复杂但灵活，难度大的题）：
- 适用于需要更复杂状态管理的问题
- 详见 BFS 算法习题章节
3. 抽象思维：将问题转化为图/树结构
BFS 算法的难点不在于代码框架，而在于如何将具体问题抽象成图/树结构：
- 状态 = 节点
- 状态转移 = 边
- 初始状态 = 起点
- 目标状态 = 终点
基本原理
BFS 算法核心思想
- 队列：存储待访问的节点
- visited 集合：防止走回头路（成环）
- 按层扩散：每次处理当前层所有节点后再进入下一层
- 步数记录：每处理完一层，步数 +1
为什么 BFS 适合最短路径？
- DFS 需要遍历整棵树才能找到目标
- BFS 按层扩散，第一次到达目标时一定是最短路径
类比：二叉树最小深度问题，BFS（层序遍历）不需要遍历所有节点就能找到最近的叶子节点。
代码实现
例题一：滑动谜题（LeetCode 773）
问题描述：2x3 的滑动拼图，数字 0 表示空位，可以和上下左右的数字交换，求变成 [[1,2,3],[4,5,0]] 的最少移动次数。
抽象为图结构：
- 每个棋盘状态是一个节点
- 0 与上下左右交换得到的状态是邻居节点
- 起点：初始棋盘状态
- 终点：
[[1,2,3],[4,5,0]]
关键技巧：
- 将二维数组序列化为字符串，便于存入哈希集合
- 预处理一维索引的邻居映射（对于 m x n 的棋盘）
完整代码：
class Solution {
public int slidingPuzzle(int[][] board) {
int m = 2, n = 3;
StringBuilder sb = new StringBuilder();
String target = "123450";
// 将 2x3 的数组转化成字符串作为 BFS 的起点
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
sb.append(board[i][j]);
}
}
String start = sb.toString();
// 记录一维字符串的相邻索引
int[][] neighbor = new int[][]{
{1, 3},
{0, 4, 2},
{1, 5},
{0, 4},
{3, 1, 5},
{4, 2}
};
// ****** BFS 算法框架开始 ******
Queue<String> q = new LinkedList<>();
HashSet<String> visited = new HashSet<>();
// 从起点开始 BFS 搜索
q.offer(start);
visited.add(start);
int step = 0;
while (!q.isEmpty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
String cur = q.poll();
// 判断是否达到目标局面
if (target.equals(cur)) {
return step;
}
// 找到数字 0 的索引
int idx = 0;
for (; cur.charAt(idx) != '0'; idx++) ;
// 将数字 0 和相邻的数字交换位置
for (int adj : neighbor[idx]) {
String new_board = swap(cur.toCharArray(), adj, idx);
// 防止走回头路
if (!visited.contains(new_board)) {
q.offer(new_board);
visited.add(new_board);
}
}
}
step++;
}
// ****** BFS 算法框架结束 ******
return -1;
}
private String swap(char[] chars, int i, int j) {
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
return new String(chars);
}
}
通用邻居映射生成函数（适用于任意 m x n 棋盘）：
int[][] generateNeighborMapping(int m, int n) {
int[][] neighbor = new int[m * n][];
for (int i = 0; i < m * n; i++) {
List<Integer> neighbors = new ArrayList<>();
// 如果不是第一列，有左侧邻居
if (i % n != 0) neighbors.add(i - 1);
// 如果不是最后一列，有右侧邻居
if (i % n != n - 1) neighbors.add(i + 1);
// 如果不是第一行，有上方邻居
if (i - n >= 0) neighbors.add(i - n);
// 如果不是最后一行，有下方邻居
if (i + n < m * n) neighbors.add(i + n);
neighbor[i] = neighbors.stream().mapToInt(Integer::intValue).toArray();
}
return neighbor;
}
例题二：打开转盘锁（LeetCode 752）
问题描述：四位密码锁，每次可以转动一位（0-9 循环），不能转到 deadends 中的密码，求从 "0000" 到 target 的最少转动次数。
抽象为图结构：
- 每个密码是一个节点（4 位字符串）
- 每位向上/向下转动得到 8 个邻居节点
- 起点："0000"
- 终点：target
完整代码：
class Solution {
public int openLock(String[] deadends, String target) {
// 记录需要跳过的死亡密码
Set<String> deads = new HashSet<>();
for (String s : deadends) deads.add(s);
if (deads.contains("0000")) return -1;
// 记录已经穷举过的密码，防止走回头路
Set<String> visited = new HashSet<>();
Queue<String> q = new LinkedList<>();
// 从起点开始启动广度优先搜索
int step = 0;
q.offer("0000");
visited.add("0000");
while (!q.isEmpty()) {
int sz = q.size();
// 将当前队列中的所有节点向周围扩散
for (int i = 0; i < sz; i++) {
String cur = q.poll();
// 判断是否到达终点
if (cur.equals(target))
return step;
// 将一个节点的合法相邻节点加入队列
for (String neighbor : getNeighbors(cur)) {
if (!visited.contains(neighbor) && !deads.contains(neighbor)) {
q.offer(neighbor);
visited.add(neighbor);
}
}
}
// 在这里增加步数
step++;
}
// 如果穷举完都没找到目标密码，那就是找不到了
return -1;
}
// 将 s[j] 向上拨动一次
String plusOne(String s, int j) {
char[] ch = s.toCharArray();
if (ch[j] == '9')
ch[j] = '0';
else
ch[j] += 1;
return new String(ch);
}
// 将 s[i] 向下拨动一次
String minusOne(String s, int j) {
char[] ch = s.toCharArray();
if (ch[j] == '0')
ch[j] = '9';
else
ch[j] -= 1;
return new String(ch);
}
// 将 s 的每一位向上拨动一次或向下拨动一次，8 种相邻密码
List<String> getNeighbors(String s) {
List<String> neighbors = new ArrayList<>();
for (int i = 0; i < 4; i++) {
neighbors.add(plusOne(s, i));
neighbors.add(minusOne(s, i));
}
return neighbors;
}
}
对比分析
双向 BFS 优化
核心思想：从起点和终点同时开始扩散，当两边有交集时停止。
为什么更快：
- 传统 BFS：从起点单向扩散，可能遍历整棵树
- 双向 BFS：起点和终点双向奔赴，更快相遇
局限性：
- 必须知道终点在哪里才能使用
- 如二叉树最小深度问题，终点（最近的叶子节点）事先未知，无法使用
双向 BFS 代码：
class Solution {
public int openLock(String[] deadends, String target) {
Set<String> deads = new HashSet<>();
for (String s : deadends) deads.add(s);
// base case
if (deads.contains("0000")) return -1;
if (target.equals("0000")) return 0;
// 用集合不用队列，可以快速判断元素是否存在
Set<String> q1 = new HashSet<>();
Set<String> q2 = new HashSet<>();
Set<String> visited = new HashSet<>();
int step = 0;
q1.add("0000");
visited.add("0000");
q2.add(target);
visited.add(target);
while (!q1.isEmpty()) {
// 在这里增加步数
step++;
// 哈希集合在遍历的过程中不能修改，所以用 newQ1 存储邻居节点
Set<String> newQ1 = new HashSet<>();
// 获取 q1 中的所有节点的邻居
for (String cur : q1) {
// 将一个节点的未遍历相邻节点加入集合
for (String neighbor : getNeighbors(cur)) {
// 判断是否到达终点
if (q2.contains(neighbor)) {
return step;
}
if (!visited.contains(neighbor) && !deads.contains(neighbor)) {
newQ1.add(neighbor);
visited.add(neighbor);
}
}
}
// newQ1 存储着 q1 的邻居节点
q1 = newQ1;
// 因为每次 BFS 都是扩散 q1，所以把元素数量少的集合作为 q1
if (q1.size() > q2.size()) {
Set<String> temp = q1;
q1 = q2;
q2 = temp;
}
}
return -1;
}
// plusOne, minusOne, getNeighbors 方法同上
}
双向 BFS 的三个细节：
- 使用哈希集合而非队列，方便快速判断交集
- 在计算出邻居节点时就判断是否到达终点
- 每次选择元素数量少的集合进行扩散，减少搜索空间
复杂度分析：
- 时间复杂度：理论上都是 O(N)，但双向 BFS 实际运行更快
- 空间复杂度：双向 BFS 可以更快相遇，减少同时存储的节点数
应用场景
- 最短路径问题：迷宫最短路径、连连看最少拐点
- 状态搜索：密码锁最小转动次数、拼图最少步数
- 转化类问题：单词转换（每次替换一个字符）、基因变化序列
相关题目
| 平台 | 题目 | 难度 |
|---|---|---|
| LeetCode | 773. Sliding Puzzle | Medium |
| 力扣 | 773. 滑动谜题 | 中等 |
| LeetCode | 752. Open the Lock | Medium |
| 力扣 | 752. 打开转盘锁 | 中等 |
相关概念
- BFS：广度优先搜索，按层级扩散的图遍历算法
- DFS：深度优先搜索，沿路径深入到底再回溯
- 最短路径：BFS 适合求解的最短路径问题
- 层序遍历：二叉树的层序遍历是 BFS 的基础
- 图：BFS 算法操作的对象数据结构
- 哈希集合：用于记录 visited 节点，防止走回头路
- 队列：BFS 的核心数据结构，实现按层扩散
- 双向BFS：本文首次出现，暂不创建独立页
相关实体
- labuladong：本文作者，算法学习平台
总结
BFS 算法的本质是二叉树的层序遍历扩展到图结构。掌握 BFS 通用框架后，关键在于将具体问题抽象为图/树结构：状态作为节点，状态转移作为边。对于最短路径类问题，BFS 按层扩散的特性使其天然适合。遇到复杂问题时，可考虑双向 BFS 优化，但前提是必须知道终点位置。