时隔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

这次就写到这里啦！