一篇搞定广搜BFS
【摘要】 核心框架BFS 的核心思想应该不难理解的，就是把一些问题抽象成图，从一个点开始，向四周开始扩散。一般来说，我们写 BFS 算法都是用「队列」这种数据结构，每次将一个节点周围的所有节点加入队列。BFS 相对 DFS 的最主要的区别是：BFS 找到的路径一定是最短的，但代价就是空间复杂度比 DFS 大很多我们先举例一下 BFS 出现的常见场景好吧，问题的本质就是让你在一幅「图」中找到从起点sta...
核心框架
BFS 的核心思想应该不难理解的，就是把一些问题抽象成图，从一个点开始，向四周开始扩散。一般来说，我们写 BFS 算法都是用「队列」这种数据结构，每次将一个节点周围的所有节点加入队列。
BFS 相对 DFS 的最主要的区别是：BFS 找到的路径一定是最短的，但代价就是空间复杂度比 DFS 大很多
我们先举例一下 BFS 出现的常见场景好吧，问题的本质就是让你在一幅「图」中找到从起点start到终点target的最近距离，这个例子听起来很枯燥，但是 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++;
}
}
队列q就不说了，BFS 的核心数据结构；cur.adj()泛指cur相邻的节点，比如说二维数组中，cur上下左右四面的位置就是相邻节点；visited的主要作用是防止走回头路，大部分时候都是必须的，但是像一般的二叉树结构，没有子节点到父节点的指针，不会走回头路就不需要visited。例题
题1最短路径问题
//给定一个 N×M 的网格迷宫 G。G 的每个格子要么是道路，要么是障碍物（道路用1 表示，障碍物用 0 表示）。
//已知迷宫的入口位置为 (x1,y1)，出口位置为 (x2,y2)问从入口走到出口，最少要走多少个格子。
//输入第 1 行包含两个正整数 N,M，分别表示迷宫的大小。
//接下来输入一个 N×M的矩阵。若 G{i,j}=1 表示其为道路，否则表示其为障碍物。
//最后一行输入四个整数 x1,y1,x2,y2，表示入口的位置和出口的位置。首先定义一些固定的内容
static int[][] arr;//存储地图的二维数组
static int[][] bool;//辅助数组，访问过为1，没访问过为0
static int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};//上下左右
//在bfs中，一般会借助结点去解题
public static class Node{
int x,y;//坐标
int stmp;//变量
}
//地图的行 列
static int row,col;
bfs代码
public static int dfs() {
Queue<Node> queue = new LinkedList<>();//创建队列
queue.offer(start);//将首结点入队
while(!queue.isEmpty()) {//判断队列是否空
Node top = queue.poll();//出队
if(top.x==end.x&&top.y==end.y) {//判断是否满足边界，满足边界就返回
return top.stmp;
}
for(int i=0;i<4;i++) {//该结点的扩展，上下左右，根据题意来
int dx = top.x+dir[i][0];//扩展后的x坐标
int dy = top.y+dir[i][1];//扩展后的y坐标
if(test(dx,dy)) {//判断扩展后是否满足条件
Node node = new Node();
node.x = dx;
node.y = dy;
node.stmp = top.stmp+1;
queue.offer(node);//将新结点入队
bool[dx][dy] = 1;//标记该结点已经访问过
}
}
}
return -1;
}好了，到这里懂了一些了吧？下面再练几道例题，相信自己尝试着独立思考，一定可以掌握bfs
练习
题1
题目描述
小明有一块空地，他将这块空地划分为 n 行 m 列的小块，每行和每列的长度都为 1。
小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。
这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它将向自己的上、下、左、右四小块空地扩展，
这四小块空地都将变为有草的小块。请告诉小明，k 个月后空地上哪些地方有草。
输入描述
输入的第一行包含两个整数 n, m。
接下来 n 行，每行包含 m 个字母，表示初始的空地状态，字母之间没有空格。如果为小数点，表示为空地，如果字母为 g，表示种了草。
接下来包含一个整数 k。 其中 2≤n,m≤1000，1≤k≤1000。
输出描述
输出 n 行，每行包含 m 个字母，表示 k 个月后空地的状态。如果为小数点，表示为空地，如果字母为 g，表示长了草。
示例
输入
4 5
.g…
…
…g…
…
2
输出
gggg.
gggg.
ggggg
.ggg.
//这道题就是典型的广搜问题，同时向四周扩散，可以说深搜是一条线 那广搜是一个面，再简单点说，深搜是个体出动，广
搜就是群体出动了
static char[][] chars;
static int[][] bool;
static int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
static int row,col;
static int k;
public static Node{
int x,y;
int stmp;
public Node(int x,int y,int stmp){
this.x = x;
this.y = y;
this.stmp = stmp;
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
row = sc.nextInt();
col = sc.nextInt();
chars = new char[row][col];
bool = new int[row][col];
for(int i=0;i<row;i++){
String s = sc.nextLine();
String[] str = s.split(" ");
for(int j=0;j<col;j++){
chars[i][j] = (char)str[j];
}
}
k = sc.nextInt();
dfs();
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
System.out.print(arr[i][j]+" ");
}
System.out.println();
}
}
public static void bfs(){
Queue<Node> queue = new LinkedList<>();
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(chars[i][j]=='g'){
queue.offer(new Node(i,j,0));
}
}
}
while(!queue.isEmpty()){
Node node = queue.poll();
if(node.stmp==2){
continue;
}
for(int i=0;i<4;i++){
int dx = node.x+dir[i][0];
int dy = node.y+dir[i][1];
int nstmp = node.stmp+1;
if(dx<0||dx>=row||dy<0||dy>=col){
continue;
}
if(bool[dx][dy]==1){
continue;
}
chars[dx][dy] = 'g';
bool[dx][dy] = 1;
queue.offer(new Node(dx,dy,nstmp));
}
}
}题2
下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可以通行的地方。
010000
000100
001001
110000
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。
对于上面的迷宫，从入口开始，可以按 DRRURRDDDR 的顺序通过迷宫， 一共 10 步。其中 D、U、L、R分别表示向下、向上、向左、向右走。 对于下面这个更复杂的迷宫（30 行 50 列），请找出一种通过迷宫的方式，其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。
请注意在字典序中 D<L<R<U
01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000
//这道题主要在于最短路和字典序最下的路径
//首先最短路问题，想到用广搜作，然后字典序，题中也给过你了，D<L<R<U，因此，只需要扩展情况的时候，按照这个顺序来，那么最后选出来的路径一定也是字典序最小的。
public class 迷宫 {
static int[][] arr = new int[30][50];
static int[][] bool = new int[30][50];
static int[][] dir = {{1,0},{0,-1},{0,1},{-1,0}};
//按字典序顺序来写
static String[] chars = {"D","L","R","U"};
public static class Node {
int x,y;
String stmp;
public Node() {}
public Node(int x,int y,String s) {
this.x = x;
this.y = y;
this.stmp = s;
}
}
static Node start = new Node();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
for(int i=0;i<30;i++) {
String s = sc.nextLine();
String[] str = s.split("");
for(int j=0;j<50;j++) {
arr[i][j] = Integer.parseInt(str[j]);
}
}
start.x = 0;start.y = 0;start.stmp = "";
bfs(start);
}
public static boolean test(int x,int y) {
if(x<0||x>29||y<0||y>49) return false;
if(arr[x][y]==1) return false;
if(bool[x][y]==1) return false;
return true;
}
public static void bfs(Node start) {
Queue<Node> queue = new LinkedList<>();
queue.offer(start);
bool[start.x][start.y] = 1;
String s = "";
while(!queue.isEmpty()) {
Node node = queue.poll();
if(node.x==29&&node.y==49) {
s = node.stmp;
break;
}
for(int i=0;i<4;i++) {
int dx = node.x+dir[i][0];
int dy = node.y+dir[i][1];
if(dx>=0&&dx<=29&&dy>=0&&dy<=49&&arr[dx][dy]=='0'&&bool[dx][dy]!=1){
queue.offer(new Node(dx, dy, node.stmp+chars[i]));
bool[dx][dy]=1;
}
}
}
System.out.println(s);
}
}总结
以前没接触过bfs的同学，如果看到这里，真的已经很厉害了，而且我相信，各位把例题全部动手敲一遍，对照着模板想一遍，你肯定能掌握大部分了，加油，广搜必拿下！！
送给大家一句话
乾坤未定，你我解释黑马！！！
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）