BFS算法套路
# BFS算法套路框架
广度优先搜素
(BFS)和深度优先搜素
(DFS)是图遍历的两种经典算法,DFS是向下越来越深入,而BFS就是四处扩散越来越开拓。
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 sz = q.size();
/* 将当前队列中的所有节点向四周扩散 */
for (int i = 0; i < sz; 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()表示与当前结点相连的节点。
visited
的主要作用是防止走回头路,大部分时候都是必须的,但是像一般的二叉树结构,没有子节点到父节点的指针,不会走回头路就不需要visited
。
题目:
111. 二叉树的最小深度 (opens new window)
# 二叉树的最小深度
题目:
思想:
最小深度其实可以使用递归来解决,但是这里我们就使用BFS
。那么题目条件如何转为最短路径呢?最小深度就是根节点到叶节点最短路径。
代码:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
// 当前节点能够连接的节点队列
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int depth = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for(int i = 0; i < size; i++) {
// 当前节点
TreeNode current = queue.poll();
// 如果是叶节点
if(current.left == null && current.right == null) {
return depth;
}
// 将当前节点所连接的节点加入节点队列
if(current.left != null) {
queue.offer(current.left);
}
if(current.right != null) {
queue.offer(current.right);
}
}
depth++;
}
return depth;
}
}
# 打开转盘锁
题目:
思想:
这个类似我们的密码箱,有四个位置,然后每次调整一个位置,且一个位置的数字只能跳转一次。相当于我们在这种情况下要找最快解密的方法,且同时在解密的过程中要避免死亡字符串。
我们把每一个字符串当作一个节点,那么它相邻的节点是什么?
比如0000,就有8个相邻的节点:0001,0010,0100,1000,9000,0900,0090,0009。前四个是向上调整,后四个是向下调整。
这样我们就可以每次遍历一个节点之后,把该节点的相邻节点(无重复节点)添加到节点队列,使用模板即可。
代码:
class Solution {
public int openLock(String[] deadends, String target) {
Set<String> deadensList = new HashSet<>();
// 所有死亡字符串加入set集合
deadensList.addAll(Arrays.asList(deadends));
// 当前节点队列
Queue<String> queue = new LinkedList<>();
// 访问过的节点队列
Set<String> visited = new HashSet<>();
queue.offer("0000");
visited.add("0000");
int step = 0;
while(!queue.isEmpty()) {
// 当前队列的大小
int size = queue.size();
for(int i = 0; i < size; i++) {
// 当前的字符串
String current = queue.poll();
// 避开所有死亡字符串
if(deadensList.contains(current)) {
continue;
}
if(current.equals(target)) {
return step;
}
// 将临近的节点加入节点队列
for(int j = 0; j < 4; j++) {
// 向上的四个临近节点
String upStr = up(current, j);
if(!visited.contains(upStr)) {
queue.offer(upStr);
visited.add(upStr);
}
// 向下的四个临近节点
String downStr = down(current, j);
if(!visited.contains(downStr)) {
queue.offer(downStr);
visited.add(downStr);
}
}
}
step++;
}
return -1;
}
/**
* 向上调整
*/
String down(String src, int j) {
char[] ch = src.toCharArray();
if(ch[j] == '0') {
ch[j] = '9';
} else {
ch[j] -= 1;
}
return new String(ch);
}
/**
* 向下调整
*/
String up(String src, int j) {
char[] ch = src.toCharArray();
if(ch[j] == '9') {
ch[j] = '0';
} else {
ch[j] += 1;
}
return new String(ch);
}
}
# 参考
上次更新: 2024/06/29, 15:13:44