Algorithm进阶计划 -- 广度优先算法
广度优先算法
- 广度优先算法框架
- 广度优先算法运用
图片来源于网络
1. 广度优先算法框架
DFS（Deep First Search）深度优先搜索，跟之前介绍的回溯算法没啥差。
BFS（Breath First Search）广度优先搜索，和 DFS 主要区别是：BFS 找到的路径一定是最短的，但代价就是空间复杂度比 DFS 大很多。
BFS 出现的常见场景，其问题的本质就是在一幅「图」中找到从起点 start 到终点 target 的最近距离，如走迷宫、连连看等。
BFS 框架如下：
/**
* 计算从起点 start 到终点 target 的最近距离
*/
int BFS(Node start, Node target) {
Queue<Node> q; // 核心数据结构
Set<Node> visited;// 避免走回头路
q.offer(start); // 将起点加入队列
visited.add(start);
int step = 0; // 记录扩散的步数
while (q not empty) {
int size = q.size();
// 将当前队列中的所有节点向四周扩散
for (int i = 0; i < size; i++) {
Node cur = q.poll();
// 划重点：这里判断是否到达终点
if (cur is target) {
return step;
}
// 将 cur 的相邻节点加入队列
for (Node x : cur.adj()) {
if (x not in visited){
q.offer(x);
visited.add(x);
}
}
}
// 划重点：更新步数在这里
step++;
}
}
}
上面值得注意的是，cur.adj() 泛指 cur 相邻的节点，如在二维数组中 cur 上下左右四面的位置就是相邻节点；visited 的作用是防止走回头路，但在一般的二叉树结构中，无子节点到父节点的指针，不会走回头路就不需要 visited。
2. 广度优先算法运用
2.1 二叉树的最小深度
力扣 111 题如下：
二叉树的最小深度
首先，明确一下起点 start 和终点 target 是什么，显然起点就是 root 根节点，终点就是最靠近根节点的叶子节点，叶子节点判断如下：
// 叶子节点就是两个子节点都是 null 的节点
if (cur.left == null && cur.right == null)
// 到达叶子节点
接着，套用 BFS 框架实现如下：
/**
* 二叉树最小深度
*/
public int minDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
// root 本身就是一层，depth 初始化为 1
int depth = 1;
while (!q.isEmpty()) {
int size = q.size();
// 将当前队列中的所有节点向四周扩散
for (int i = 0; i < size; i++) {
TreeNode cur = q.poll();
// 划重点：这里判断是否到达终点
if (cur.left == null && cur.right == null) return depth;
// 将 cur 的相邻节点加入队列
if (cur.left != null) q.offer(cur.left);
if (cur.right != null) q.offer(cur.right);
}
// 划重点：更新步数在这里
depth++;
}
return depth;
}
上面值得注意的是，depth 每增加一次，队列中的所有节点都向前迈一步，保证了第一次到达终点时走的步数是最少的。
2.2 打开转盘锁
力扣 752 题如下：
打开转盘锁
若不管不管 deadends 和 target 的限制，穷举所有可能的密码组合，考虑到共有4个位置，每个位置转动一次可以向上或向下转动，即有8种可能，因此可以抽象成一幅图，每个节点有 8 个相邻的节点，求最少转动次数，套用 BFS 框架如下：
/**
* BFS 框架，打印出所有可能的密码
*/
void BFS(String target) {
Queue<String> q = new LinkedList<>();
q.offer("0000");
while (!q.isEmpty()) {
int size = q.size();
// 将当前队列中的所有节点向周围扩散
for (int i = 0; i < size; i++) {
String cur = q.poll();
// 判断是否到达终点
System.out.print(cur);
// 将一个节点的相邻节点加入队列
for (int j = 0; j < 4; j++) {
String up = plusOne(cur, j);
String down = minusOne(cur, j);
q.offer(up);
q.offer(down);
}
}
// 在这里增加步数
}
return;
}
/**
* 将 s[i] 向上拨动一次
*/
String plusOne(String s, int i) {
char[] ch = s.toCharArray();
if (ch[i] == '9') ch[i] = '0';
else ch[i] += 1;
return new String(ch);
}
/**
* 将 s[i] 向下拨动一次
*/
String minusOne(String s, int i) {
char[] ch = s.toCharArray();
if (ch[i] == '0') ch[i] = '9';
else ch[i] -= 1;
return new String(ch);
}
上面代码能够穷举所有可能的密码组合了，接下来处理题目中的如下问题：
- 会走回头路。(如从"0000"拨到"1000"，等从队列拿出"1000"时，还会拨出一个"0000"，产生死循环)
- 终止条件。
- 对
deadends的处理。
修改代码修复这些问题如下：
/**
* 打开转盘锁
*/
public int openLock(String[] deadends, String target) {
// 记录需要跳过的死亡密码
Set<String> deads = new HashSet<>();
for (String s : deadends) deads.add(s);
// 记录已经穷举过的密码，防止走回头路
Set<String> visited = new HashSet<>();
Queue<String> q = new LinkedList<>();
// 从起点开始启动广度优先搜索
int step = 0;
q.offer("0000");
visited.add("0000");
while (!q.isEmpty()) {
int size = q.size();
// 将当前队列中的所有节点向周围扩散
for (int i = 0; i < size; i++) {
String cur = q.poll();
// 判断是否到达终点
if (deads.contains(cur)) continue;
if (cur.equals(target)) return step;
// 将一个节点的相邻节点加入队列
for (int j = 0; j < 4; j++) {
String up = plusOne(cur, j);
if (!visited.contains(up)) {
q.offer(up);
visited.add(up);
}
String down = minusOne(cur, j);
if (!visited.contains(down)) {
q.offer(down);
visited.add(down);
}
}
}
// 在这里增加步数
step++;
}
// 如果穷举完都没找到目标密码，那就是找不到了
return -1;
}
2.3 滑动谜题
力扣 773 题如下：
滑动谜题
上面题目例子中，比如输入 board = [[4,1,2],[5,0,3]]，可用如下直观展示过程：
board = [[4,1,2],[5,0,3]]
BFS 算法并不只是一个寻路算法，而是一种暴力搜索算法，只要涉及暴力穷举的问题，BFS 就可以用。
这道题其实是一个 BFS 问题，每次先找到数字 0，然后和周围的数字进行交换，形成新的局面加入队列... 当第一次到达 target 时就得到了最少步数。
这里的 board 是 2x3 的二维数组，可以压缩成一个一维字符串，然后写一个映射对应某一个索引上下左右的索引：
int[][] neighbor = new int[][]{
{1, 3},
{0, 4, 2},
{1, 5},
{0, 4},
{3, 1, 5},
{4, 2}
};
即在一维字符串中，索引 i 在二维数组中的的相邻索引为 neighbor[i]：
相邻索引映射
接着，就可以套用 BFS 算法框架实现代码如下：
/**
* 滑动谜题
*/
public int slidingPuzzle(int[][] board) {
int m = 2, n = 3;
// 将 2x3 的数组转化成字符串
StringBuilder sb = new StringBuilder();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
sb.append(board[i][j]);
}
}
String start = sb.toString();
String target = "123450";
// 记录一维字符串的相邻索引
int[][] neighbor = new int[][]{
{1, 3},
{0, 4, 2},
{1, 5},
{0, 4},
{3, 1, 5},
{4, 2}
};
// BFS 算法框架开始
Queue<String> q = new LinkedList<>();
Set<String> visited = new HashSet<>();
q.offer(start);
visited.add(start);
int step = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
String cur = q.poll();
// 判断是否达到目标局面
if (cur.equals(target)) return step;
// 找到数字 0 的索引
int index = 0;
while (cur.charAt(index) != '0') {
index++;
}
// 将数字 0 和相邻的数字交换位置
for (int adj : neighbor[index]) {
char[] temp = cur.toCharArray();
temp[adj] = cur.charAt(index);
temp[index] = cur.charAt(adj);
String new_board = new String(temp);
// 防止走回头路
if (!visited.contains(new_board)) {
q.offer(new_board);
visited.add(new_board);
}
}
}
step++;
}
return -1;
}
小结：
DFS 算法和回溯算法的核心思路是相同的，逻辑上都是在遍历一棵树。
BFS 也是一个暴力搜索算法，只不过把递归改成了迭代，利用一个队列进行穷举而已。
参考链接：
