迷宫问题Java实现（BFS和DFS 迷宫问题
迷宫问题算是经常会碰到的，类似于下图，这是一个5x5的迷宫，这里数字1代表可以走的路，数字0代表不可以走的路，从（0，0）到（4，4）显然有两条路径。
在这里插入图片描述
1， DFS求迷宫路径
DFS（Depth-First-Search，深度优先搜索），顾名思义总是选择深度大的节点去访问，下面的图是一个二叉树，如果从头结点F开始深度优先遍历，若访问了C则下一个节点不可能是E，因为C和E的深度是一样的，违反深度优先原则。深度优先遍历序列不唯一。 在这里插入图片描述 ok，现在我们来用深度优先来解决迷宫问题，这里用到了回溯法 伪代码：
public void dfs(int m,int n,int rounds) {//m n 分别为 当前点 横坐标和纵坐标
if(m==4 && n==4) {
输出路径和步数
}
if(数字1){//可访问
将数字1变为数字0//访问过不再访问
判断上下左右能否访问，若能 dfs（）递归调用
回溯（将数字0变为数字1）
}
}
2， BFS求迷宫最短路径
BFS（Breadth First Search，宽度优先搜索），对于上面的二叉树，如果从头结点F开始深度优先遍历，若访问了C则下一个节点一定是E，由于先访问的结点C所以接下来访问的一定是C的子节点。宽度优先遍历序列不唯一。 伪代码：
public void bfs(int m,int n) {//m n 分别为 目标点 横坐标和纵坐标
起点入队
while（队不为空）{
出队
若到目标点->输出步数
判断上下左右能否访问，若能则入队
}
输出路径
}
3， 源码（DFS+BFS）
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
public class BFSTest {
private static int data[][] = new int[5][5];
private Stack<Node1> stack1 = new Stack<Node1>();
private List<Node1> list = new ArrayList<Node1>();//存储dfs第一条到达目标点的路径
private boolean flag=true;// 辅助判断 存储dfs第一条到达目标点的路径
private int next[][] = { { 0, 1 }, { 1, 0 } ,{0,-1},{-1,0}};// 4个方向
class Node {//bfs
int row;
int column;
int father_x;
int father_y;
int round;
public Node(int row, int column,int father_x, int father_y, int round) {
super();
this.row = row;
this.column = column;
this.father_x= father_x;
this.father_y = father_y;
this.round = round;
}
}
class Node1{//dfs
int row;
int column;
int father_x;
int father_y;
public Node1(int row, int column,int father_x, int father_y) {
super();
this.row = row;
this.column = column;
this.father_x= father_x;
this.father_y = father_y;
}
}
public void dfs(int m,int n,int rounds) {//m n 分别为 当前点 横坐标和纵坐标
if(m==4 && n==4) {
if(flag) {//flag: 第一个出口路线
Node1 node1 = stack1.pop();
int a=node1.father_x;
int b=node1.father_y;
System.out.println(""+node1.row+"-"+node1.column);
while(!stack1.isEmpty()) {
Node1 node3 = stack1.pop();
if(node3.row==a && node3.column==b) {
System.out.println(""+node3.row+"-"+node3.column);
a=node3.father_x;
b=node3.father_y;
}
}
//System.out.println(""+0+"-"+0);
}else {
Node1 node1 = stack1.pop();
int a=node1.father_x;
int b=node1.father_y;
int t=0;
System.out.println(""+node1.row+"-"+node1.column);
while(!stack1.isEmpty()) {
Node1 node3 = stack1.pop();
if(node3.row==a && node3.column==b) {
System.out.println(""+node3.row+"-"+node3.column);
a=node3.father_x;
b=node3.father_y;
}
}
//寻找第一个分叉点
for(int i=0;i<list.size();i++) {
if(list.get(i).row==a && list.get(i).column==b) {
t=i;
break;
}
}
//输出分叉点前的点
for(int i=t;i>=0;i--) {
System.out.println(list.get(i).row+"-"+list.get(i).column);
}
}
System.out.println(rounds);
flag=false;
}
if(data[m][n]==1) {
data[m][n]=0;
//stack1.push(new Node1(m,n));
for(int i=0;i<4;i++) {
int temp1 = m+next[i][0];
int temp2 = n+next[i][1];
if(temp1>4 || temp2>4 || temp1<0 || temp2<0 ||data[temp1][temp2]==0) {
continue;
}
if(flag) {
list.add(new Node1(temp1,temp2,m,n));
}
stack1.push(new Node1(temp1,temp2,m,n));
dfs(temp1,temp2,rounds+1);//递归
}
data[m][n]=1;//回溯
}
}
public void bfs(int m,int n) {//m n 分别为 目标点 横坐标和纵坐标
Queue<Node> queue = new LinkedList<>();
Node node1 = new Node(0, 0,-1,-1, 0);
Stack<Node> stack = new Stack<Node>();//存访问过的结点
queue.offer(node1);
while(!queue.isEmpty()) {
Node node2 = queue.poll();
stack.push(node2);
if(node2.row==m && node2.column==n) {
System.out.println(node2.round);
break;
}
for(int i=0;i<4;i++) {
int temp1 = node2.row+next[i][0];
int temp2 = node2.column+next[i][1];
if(temp1>4 || temp2>4 || temp1<0 || temp2<0 ||data[temp1][temp2]==0) {
continue;
}
data[temp1][temp2]=0;
queue.offer(new Node(temp1,temp2,node2.row,node2.column,node2.round+1));
}
}
Node node = stack.pop();
int a=node.father_x;
int b=node.father_y;
System.out.println(""+node.row+"-"+node.column);
while(!stack.isEmpty()) {
Node node3 = stack.pop();
if(node3.row==a && node3.column==b) {
System.out.println(""+node3.row+"-"+node3.column);
a=node3.father_x;
b=node3.father_y;
}
}
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
/*
10000
10111
11101
00001
00001
*/
for(int i=0;i<5;i++) {
String ss = s.nextLine();
for(int j=0;j<5;j++) {
data[i][j]=Integer.parseInt(ss.charAt(j)+"");
}
}
new BFSTest().bfs(4,4);
//new BFSTest().dfs(0,0,0);
}
}
备注： 1，dfs输出所有路径长度以及具体路径。bfs输出最短路径长度和具体路径 2，dfs可能存在多条路径，需要先存储第一条到达目标点的路径，这里用list来存储。第一条路径输出后，这时用于存储路径的栈已经是个空栈了，在第二次访问到目标点时，栈中只有两条路径相交点到目标点的具体路径，这时再遍历list就可以找到起点到相交点这段具体路径了。
4， 输入输出
1，输入
10000
10111
11101
10001
11111
12345
2，bfs输出
8
4-4
4-3
4-2
4-1
4-0
3-0
2-0
1-0
0-0
3，dfs输出
4-4
3-4
2-4
1-4
1-3
1-2
2-2
2-1
2-0
1-0
10
4-4
4-3
4-2
4-1
4-0