目录导航

问题描述BFS原理（BFS：广度优先搜索）Java实现C++实现

问题描述

如下图，找到从（1,1）到（6,5）的最短路径。

BFS原理（BFS：广度优先搜索）

故事设定：走格子策略为下右上左，给我个面子，假装迷宫自带十万倍重力buff，他们飞不起来😄

某天太阳高照，天气炎热，唐僧四人走走停停，来到一迷宫附近，发现必要要经过迷宫才能过去，于是乎，几人商定后，在起点由猴哥走下，沙僧走右，八戒走上，白龙马走右，师傅原地休息，八戒哈哈一笑，看着上面的墙与师傅一起坐在原地，道：“猴哥，老沙，靠你们了，我上方位是墙，走不了。”白龙马也叫着，表达自己的兴奋。毕竟十万倍重力不是开玩笑的。（起点[1][1]入队）

猴哥沙僧相识无奈一笑，开始他们探索迷宫的第一步。起点[1][1]出队，即出队头，点[1][2]和[2][1]入队

接着点[1][2]出队头，其下，左都是墙不能走，上之前已经走过，就不走了，所以只能走右。所以点[2][2]入队。

接着按照走poll出的队头四方位相邻无墙初次走的格子，直到找到终点（我们设定的），或者队列为空（这种情况表示起点无路径走到终点）。

BFS在此题的核心就是几个人同时探索走向终点的不同路径，谁先找到谁找的那条最短，

即在前往同一地点的过程中，速度相同，谁先到，谁的路程最短。

Java实现

package demo;import java.util.LinkedList;import java.util.Queue;public class MiGongBFS {public static void main(String[] args) {// 构建迷宫上下围墙int[][] array = new int[8][7];int[][] temp = new int[8][7];for (int i = 0; i < 7; i++) {array[0][i] = 1;array[7][i] = 1;}// 设置挡板，此处可自行变换，来模拟出不同的路径array[3][0] = 1;array[3][1] = 1;for (int i = 0; i < 8; i++) {array[i][0] = 1;array[i][6] = 1;}// 设置迷宫的左右围墙for (int i = 0; i < 8; i++) {for (int j = 0; j < 7; j++) {System.out.print(array[i][j] + " ");}System.out.println();}System.out.println();// BFSQueue<Point> q = new LinkedList<Point>();Point start = new Point();start.setX(1);start.setY(1);start.setStep(0);temp[1][1] = 1;q.offer(start);int flag = 0;// 下右上左int[] dx = {0, 1, 0, -1 };int[] dy = {1, 0, -1, 0 };while (!q.isEmpty()) {int x = q.peek().getX();int y = q.peek().getY();int step = q.peek().getStep();if (x == 6 && y == 5) {flag = 1;System.out.println("迷宫最短路径是：" + step);break;}for (int i = 0; i < 4; i++) {int tx = x + dx[i];int ty = y + dy[i];if (array[tx][ty] == 0 && temp[tx][ty] == 0) {Point t = new Point();t.setX(tx);t.setY(ty);t.setStep(step + 1);q.offer(t);temp[tx][ty] = 1;}}q.poll();}if (flag == 0) {System.out.println("找不到相应路径，即起点没有路径达到终点！");}}}

Point.java

package demo;public class Point {private int x;private int y;private int step;public int getX() {return x;}public void setX(int x) {this.x = x;}public int getY() {return y;}public void setY(int y) {this.y = y;}public int getStep() {return step;}public void setStep(int step) {this.step = step;}}

C++实现

#include <iostream>#include <queue>using namespace std;struct Point{int x;int y;int step;};int main(){int map[8][7];int temp[8][7];int i,j;for(i =0;i < 8;i++){for(j = 0;j < 7;j++){map[i][j] = 0;}}for(i =0;i < 8;i++){for(j = 0;j < 7;j++){temp[i][j] = 0;}}for(i = 0;i < 7;i++){map[0][i] = 1;map[7][i] = 1;}for(i = 0;i < 8;i++){map[i][0] = 1;map[i][6] = 1;}map[3][0] = 1;map[3][1] = 1;for(i =0;i < 8;i++){for(j = 0;j < 7;j++){cout<<map[i][j]<<" ";}cout<<endl;}// 下右上左int dx[4] = {0,1,0,-1};int dy[4] = {1,0,-1,0};Point start;start.x = 1;start.y = 1;start.step = 0;temp[1][1] = 1;queue<Point> q;q.push(start);int flag = 0;while(!q.empty()){int x = q.front().x;int y = q.front().y;int step = q.front().step;if(x == 6 && y == 5){flag = 1;cout<<"迷宫的最短路径是："<<step;cout<<endl;break;}for(int i = 0;i < 4;i++){int tx = x + dx[i];int ty = y + dy[i];if(map[tx][ty] == 0 && temp[tx][ty] == 0){Point p;p.x = tx;p.y = ty;p.step = step + 1;q.push(p);temp[tx][ty] = 1;map[tx][ty] = 2;}}q.pop();}if(flag == 0){cout<<"找不到从起点到终点的路径！"<<endl;}for(i =0;i < 8;i++){for(j = 0;j < 7;j++){cout<<map[i][j]<<" ";}cout<<endl;}return 0;}

2表示程序在从起点出发探索最短路径的过程中入过队的点。

如果觉得《迷宫问题寻找最短路径（BFS）》对你有帮助，请点赞、收藏，并留下你的观点哦！