之前使用prim生成迷宫后，想加一个寻找
最短路径
的算法，但是使用bfs算法计算走出最少需要多少步还算比较简单，但是如何记录那条最短路径却难到我了。
一个比较常见的思路是记录每个节点的父节点，然后从终点一直往前寻找他们的父节点，找到起点时停止。
BFS(广度优先算法)
这里是新建了一个宽高和迷宫地图一样的数组来存储相应位置上的父节点。
整个过程相当于一个树的分叉，如果有一个分叉找到终点，就一层一层的来找它们的父节点，形成路径。（下面的示意图源于网络，主要是体现那种树的结构）
BFS寻路部分 代码：
完整Java代码：
import java.awt.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class MazeBfs {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("请输入宽和高：");
int width = sc.nextInt();
int height = sc.nextInt();
System.out.println("迷宫宽为：" + width + "，高为：" + height);
int[][] mazearr = new int[2 * width + 1][2 * height + 1];//动态初始化
// mazearr.length 宽 mazearr[0].length) 高
for (int i = 0; i < mazearr.length; i++) { //行
for (int j = 0; j < mazearr[0].length; j++) {
if (i%2==0 || j%2 ==0){
mazearr[i][j] = 1;
}
//
//if (mazearr[i][j] == 1) {
// System.out.print(" #");
//} else {
// System.out.print(" ");
//}
}
//System.out.println();
}
// 0 路 1 墙
// 2 已访问路 list 待访问墙的列表
/*
0 1 2 3
* 1 1 1 1 1 1 1 0
* 1 * 1 0 1 0 1 1
* 1 1 1 1 1 1 1 2
* 1 0 1 0 1 0 1 3
* 1 1 1 1 1 1 1
* 1 0 1 0 1 0 1
* 1 1 1 1 1 1 1
* */
int x = 1;
int y = 1; //起始点
Point p = new Point(1,1);
ArrayList<Point> list = new ArrayList<>();
mazearr[x][y] = 2; //起始点设为已访问路
//加入邻墙
//list.add(new Point(1,2));
//list.add(new Point(2,1));
list = addWall(new Point(x,y),list,mazearr);
int r ;
while (!list.isEmpty()){
r = (int) (Math.random()*list.size());
x = list.get(r).x;
y = list.get(r).y; //墙坐标
if (mazearr[x-1][y]==0){
mazearr[x][y] = 2;
mazearr[x-1][y]=2; //空格坐标
list = addWall(new Point(x-1,y),list,mazearr);
}
if (mazearr[x+1][y]==0){
mazearr[x][y] = 2;
mazearr[x+1][y]=2;
list = addWall(new Point(x+1,y),list,mazearr);
}
if (mazearr[x][y-1]==0){
mazearr[x][y] = 2;
mazearr[x][y-1]=2;
list = addWall(new Point(x,y-1),list,mazearr);
}
if (mazearr[x][y+1]==0){
mazearr[x][y] = 2;
mazearr[x][y+1]=2;
list = addWall(new Point(x,y+1),list,mazearr);
}
list.remove(r);
}
System.out.println("生成迷宫图：");
for (int i = 0; i < mazearr.length; i++) { //行
for (int j = 0; j < mazearr[0].length; j++) {
if (mazearr[i][j] == 1 ) {
System.out.print(" #");
} else {
System.out.print(" ");
}
}
System.out.println();
}
//bfs广度优先搜索 寻路
//1为墙， 2为路， 4为已访问路
Point[][] bookarr = new Point[2 * width + 1][2 * height + 1]; //记录父类节点
//起点为1，1 终点为mazearr.length-2，mazearr[0].length-2
Queue<Point> queue = new LinkedList<>(); //创建队列
Point node = new Point(1,1); //起点
queue.offer(node); //起点加入队列
mazearr[1][1]=4; //标记为4，代表已访问
while (!queue.isEmpty()){ //队列为空时 结束
node = queue.poll(); //取出队首元素，赋值给node;
if(node.x==mazearr.length-2 && node.y== mazearr[0].length-2){ //找到终点
break;
}else {
x=node.x;
y=node.y;
// 相邻且未访问的点加入队列
//判断是否有路 上下左右
if(mazearr[x-1][y]==2){
queue.offer(new Point(x-1, y)); //加入队列
mazearr[x-1][y]=4; //标记为已访问；
bookarr[x-1][y] = new Point(x, y); //记录相应位置的父节点，用来返回路径
}
if (mazearr[x+1][y]==2){
queue.offer(new Point(x+1, y));
mazearr[x+1][y]=4;
bookarr[x+1][y] = new Point(x, y);
}
if (mazearr[x][y-1]==2){
queue.offer(new Point(x, y-1));
mazearr[x][y-1]=4;
bookarr[x][y-1] = new Point(x, y);
}
if (mazearr[x][y+1]==2){
queue.offer(new Point(x, y+1));
mazearr[x][y+1]=4;
bookarr[x][y+1] = new Point(x, y);
}
}
}
int step = 0; //记录路径步数；
//查找路径
while ((node.x!=1 || node.y!=1)){
//查找相应位置的父节点
node = bookarr[node.x][node.y];
mazearr[node.x][node.y] = 5; //相应位置标记为5，代表路径
step++;
}
System.out.println("Bfs路径步数为："+step);
System.out.println("Bfs路径：");
for (int i = 0; i < mazearr.length; i++) { //行
for (int j = 0; j < mazearr[0].length; j++) {
if ((i==1&&j==1) || (i==mazearr.length-2&&j==mazearr[0].length-2)){
System.out.print(" @");
}else if (mazearr[i][j]==5){
System.out.print(" >");
}else if (mazearr[i][j]==1){
System.out.print(" #");
}else {
System.out.print(" ");
}
}
System.out.println();
}
}
public static ArrayList<Point> addWall(Point p,ArrayList<Point> list,int[][] mazearr){ //添加邻墙
int x = p.x;
int y = p.y; //路坐标
if (0<x-2 && x-2<mazearr.length){ //上
if(mazearr[x-2][y]==0 && mazearr[x-1][y]==1){
// 加入邻墙
list.add(new Point(x-1,y));
}
}
if (0<x+2 && x+2<mazearr.length){ //
if(mazearr[x+2][y]==0 && mazearr[x+1][y]==1){
// 加入邻墙
list.add(new Point(x+1,y));
}
}
if (0<y-2 && y-2<mazearr[0].length){ //
if(mazearr[x][y-2]==0 && mazearr[x][y-1]==1){
// 加入邻墙
list.add(new Point(x,y-1));
}
}
if (0<y+2 && y+2<mazearr[0].length){ //
if(mazearr[x][y+2]==0 && mazearr[x][y+1]==1){
// 加入邻墙
list.add(new Point(x,y+1));
}
}
return list;
}
}
运行效果图：
迷宫是用的是之前prim生成的，其实用这个迷宫是体现不出来bfs能寻找最短路径的特点的，因为prim生成的迷宫任何两点都有且只有一条路径，它里面没有回路，没有多条路径。
Java 使用prim算法生成迷宫_凡梦o_o的博客-CSDN博客
这里主要是写一些用bfs寻路，并记录那个最短路径的思路。
使用java应该还有其他方法记录父节点，或者有更好的使用bfs来寻路并打印最短路径的方法。
本人是初学者，很多东西不是太懂，也不太会用。欢迎大家指点。
版权声明：本文为m0_71181165原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。