本文编写于 1418 天前,最后修改于 1418 天前,其中某些信息可能已经过时。
时隔n天又更新啦!今天想写的内容是两种搜索:Dfs和Bfs。
一、Dfs
Dfs,即深度优先搜索(Depth First Search)。顾名思义,它注重搜索的“深度”。简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次。以一个点为起点,对它的邻接点进行搜索,直到将所有与起点相通的路径全部遍历完为止。
Dfs搜索的大致结构如下:
bool Dfs(V) {
if( V 为终点)
return true;
if( V 为旧点)
return false;
将V标记为旧点;
对和V相邻的每个节点U {
if( Dfs(U) == true)
return true;
}
return false;
}
public static void main()
{
将所有点都标记为新点;
起点 = 1
终点 = 8
System.out.println(Dfs(起点));
}
例题:小明被困在了迷宫里,小李得知后立即前去解救小明。已知迷宫由n行m列的单元格组成,每个单元格要么是空地,要么是障碍物。请帮助小李找到一条从迷宫起点通往小明位置的最短路径,以便能用最快速度救出小明。
代码如下:
public class DFSS {
public int[][]a=new int[51][51];//迷宫数组
public int[][]book=new int[51][51];//用来标记哪些点已经走过
public int n,m,p,q;
public int min=99999999;
public void dfs(int x,int y,int step)
{
int [][]next={{0,1},{1,0},{0,-1},{-1,0}};//方向数组,数组里的四个元素分别代表四个前进的方向
int tx,ty,k;
if (x==p&&y==q){//判断是否到达目的地
if (step<min){
min=step;
}
return;
}
for (k=0;k<=3;k++){//把四种走法都试一次
tx=x+next[k][0];
ty=y+next[k][1];
if (tx<1||tx>n||ty<1||ty>m)//判断有没有越界
continue;
if (a[tx][ty]==0&&book[tx][ty]==0){
book[tx][ty]=1;
dfs(tx,ty,step+1);
book[tx][ty]=0;//一定要取消标记,因为尝试别的路径的时候也有可能经过这个点。
}
}
return;
}
public static void main(String args[]) {
int i,j,sx,sy;
Scanner in=new Scanner(System.in);
DFSS d=new DFSS();
d.n=in.nextInt();
d.m=in.nextInt();
for (i=1;i<=d.n;i++){
for (j=1;j<=d.m;j++){
d.a[i][j]=in.nextInt();//输入迷宫
}
}
//输入迷宫的起点坐标
sx=in.nextInt();
sy=in.nextInt();
//输入小哈所在的位置
d.p=in.nextInt();
d.q=in.nextInt();
d.book[sx][sy]=1;
d.dfs(sx,sy,0);
System.out.println(d.min);
}
输入:5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
1 1 4 3
输出:7
从这个题出发,我们不难体会出dfs方法的大致框架。
二、Bfs
Bfs,即宽度(广度)优先搜索(Breadth First Search)。顾名思义,这个算法更加注重“宽度”。目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。与dfs不同的是,bfs常使用队列的思想来实现。
同样是上面的例题,用bfs算法来解决,程序如下:
public class Bfs {
int x;//横坐标
int y;//纵坐标
int s;//走的路程
public static void main(String args[]) {
Bfs []b=new Bfs[2501];
int [][]a=new int[51][51];//迷宫数组
int [][]book=new int[51][51];//用来标记哪些点已经走过
int [][]next={{0,1},{1,0},{0,-1},{-1,0}};//方向数组
int head,tail;
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int m=in.nextInt();
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
a[i][j]=in.nextInt();
}
}
int sx=in.nextInt();
int sy=in.nextInt();
int p=in.nextInt();
int q=in.nextInt();
int tx,ty;
//初始化队列
head=1;
tail=1;
b[tail].x=sx;
b[tail].y=sy;
b[tail].s=0;
tail++;
book[sx][sy]=1;//把起点标记为已经走过
int flag=0;//标记是否到达目的点
while (head<tail){
for (int k=0;k<=3;k++){//把四种方向都枚举出来
tx=b[head].x+next[k][0];
ty=b[head].y+next[k][1];
if (tx<1||tx>n||ty<1||ty>m)//判断有没有越界
continue;
if (a[tx][ty]==0&&book[tx][ty]==0){
book[tx][ty] =1;//与深搜不同,这里不需要将book数组还原成0
b[tail].x=tx;//将新的坐标点入队
b[tail].y=ty;
b[tail].s=b[head].s+1;
tail++;
}
if (tx==p&&ty==q){//如果已经到达目的点
flag=1;
break;
}
if (flag==1)
break;
head++;//注意每次将这个点扩展完后,这个点就失去了利用价值,于是可以将它出队
}
}
System.out.println(b[tail-1].s);//输出路径 }}
输入:5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
1 1 4 3
输出:7
这次就写到这里啦!