DFS与BFS

2020.1.11

做题的时候发现自己仍是不太会运用这两种算法，所以决议仍是先把它学清楚再做题。

学习办法：看书（啊哈算法），看网站（CSDN，博客园）

DFS（深度优先查找）

dfs的完成办法：递归。

在深搜的一起考虑回溯，一次把一条路找究竟，走完或许走不通再回溯，把一切解都找出来。多用于处理一切解和连通性问题。但他的规划不能太大。查找的时候有记录走过的方位，符号完后可能要改回来。

回溯法是一种查找法，按条件向前查找，以抵达目标。但当探索到某一步时，发现原先选择达不到目标，就退回一步从头选择，这种走不通就退回再走的技术为回溯法；

dfs仍是比较好了解的，可是要在做题的时候灵活运用，把标题转化为简单模型，在模板的基础上做改动。

dfs模板：

void dfs(int step)
{
    //判别边界
    if（契合某种条件/不能持续查找了）
      {
        ...
        return ;
      }
    //尝试每一种可能
    for(i=1;i<=n;i++)
    {
     if(契合某种条件)
       {
        ...
        dfs(step+1);//递归
        ...（有时候需求把改动的条件改回来）
       }
    } 
    return ；
}

BFS（广度/宽度优先查找）

bfs的完成办法：行列。（不必自界说一个函数，因为不需求递归，直接在主函数中进行）

分治边界法，一次拜访多条路，层层递进，每一层就代表一步，每一层都需求贮存很多信息。适合处理最优解，最短路径问题。规划能够比较大。（但dfs也能够处理最短路问题，只不过效率不相同）

从一个点往每个它相邻的点走，然后在从这些路，在找能够走的路，直到最先找到契合条件的，需求用到行列。

用行列模仿过程，用结构体完成行列。

BFS的根本步骤

1. 初始化一个空行列，将初始点（一个或多个）参加一个调集尾

2. 从调集头取出点，判别初始点的周边点，将契合条件的点参加行列

3. 重复 2 操作，直至调集为空。 ( 一般 每个点只参加行列一 次 )

用一个例子来加深对bfs的了解吧（参考书：啊哈算法//我觉得这上面每个步骤讲的很清楚）

标题就是给一个地图，要求起点到结尾有多少条路径。不过多赘述了。

首先第一步，”用行列模仿过程，用结构体完成行列“，创立一个空链表，把起点入列。

struct node
{
    int x;//横坐标
    int y;//纵坐标
    int s;//步数
}que[2501];//地图巨细不超越50*50，所以行列扩展不会超越2500个
int a[51][51];//贮存地图
int book[51][51];//用book数组符号哪些点以及在行列中了，避免一个点被重复扩展。
//tip：全局变量默许一切元素初始化为0
///初始化空行列
int head=1;
int tail=1;
//将起点（1，1）入队，并符号（1，1）现已走过
que[tail].x=1;
que[tail].y=1;
que[tail].s=0;
tail++;
book[1][1]=1;

假定从（1，1）开始，先尝试往右走一步抵达了（1，2）。

tx=que[head].x;
ty=que[head].y+1;

此刻需求判别扩展点（1，2）是否越界

if(tx<1||tx>n||ty<1||ty>m)
    continue;

再判别（1，2）是否为障碍物或许现已在路径中

if(a[tx][ty]==0&&book[tx][ty]==0)
{
}

如果满意以上条件则是咱们要找的点，将它（1，2）入队，并符号该点现已走过

if(a[tx][ty]==0&&book[tx][ty]==0)
{
    //把这个点符号为现已走过
    book[tx][ty]=1;//留意宽搜每个点通常情况下只入队一次，和深搜不同，不需求将book数组复原啦。
    //刺进新扩展点
    que[tail].x=tx;
    que[tail].y=ty;
    que[tail].s=que[tail-1].s+1;//步数是父亲的步数+1
    tail++;
}

接下来还要尝试往其他方向走。咱们发现从（1，1）还能够抵达（2，1），因此咱们要把（2，1）也入队，代码完成的操作与方才相同。

这个时候对（1，1）的扩展完毕了，它对咱们来说就没用了，做个渣男，用完就丢！此刻一招将（1，1）出队。

head++；

接下来咱们就在新扩展出来的点的基础上再次扩展，直到抵达指定方位（结尾），没抵达就持续扩展。（1，1）出队之后，队首head就指向了方才扩展的第一个扩展点（1，2），咱们持续通过这个点扩展，把新的扩展点入队，扩展完这个点再把它丢了，扩展下一个点…..这样子。

为了方便向四个方向扩展呢咱们能够设置一个老朋友数组了：next数组。

int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

捋清楚这些过程，然后把这些操作组合，就得到完整代码啦！如下：

#include<stdio.h>
struct node
{
    int x;//横坐标
    int y;//纵坐标
    int s;//步数
} que[2501]; //地图巨细不超越50*50，所以行列扩展不会超越2500个
int a[51][51];//贮存地图
int book[51][51];//用book数组符号哪些点以及在行列中了，避免一个点被重复扩展。
//tip：全局变量默许一切元素初始化为0
int main()
{
    //界说一个用于表明走的方向的数组
    int next[4][2]= {{0,1},{1,0},{0,-1},{-1,0}};
    int i,j,k,n,m,startx,starty,p,q,tx,ty,flag;
    //k：用于枚举方向；n，m：地图巨细；startx，starty：起点坐标；p，q：结尾坐标；tx，ty：扩展点坐标。flag：符号是否抵达结尾。
    //输入地图
    scanf("%d %d",&n,&m);
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            scanf("%d",&a[i][j]);
    scanf("%d %d %d %d",&startx,&starty,&p,&q);//输入起点和结尾坐标
    ///初始化空行列
    int head=1;
    int tail=1;
    //往行列刺进起点坐标
    que[tail].x=startx;
    que[tail].y=starty;
    que[tail].s=0;
    tail++;
    book[startx][starty]=1;
    flag=0;
    while(head<tail)//当行列不为空时循环
    {
        //枚举4个方向
        for(k=0; k<4; k++)
        {
            tx=que[head].x+next[k][0];
            ty=que[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数组复原啦。
                //刺进新扩展点
                que[tail].x=tx;
                que[tail].y=ty;
                que[tail].s=que[head-1].s+1;//步数是父亲的步数+1
                tail++;
            }
            if(tx == p&&ty == q)//抵达结尾则推出循环
            {
                flag=1;
                break;
            }
        }
        if(flag == 1)
        {
            break;
        }
        head++;//留意这个地方前往不能忘记，当一个扩展点完毕后，head++才能对下一个扩展点进行扩展
    }
    //打印结尾最后一个点（目标点）的步数
    //留意tail是指向行列的队尾的下一个方位，所以需求减一
    printf("%d",que[tail-1].s);
    return 0;
}

别人说的好！！

（来自博客园：里昂静）//图侵删

​