关于广度优先搜索算法(BFS)题目的套路小结

2018年8月3日 13点热度 0条评论 来源: jiange702

  这两天查了很多广度优先搜索算法,看到了很多文章,感觉里面对于这种模板的讲解不够细致。首先,广度优先算法的核心是它一定是把同一级的子节点都拉入队列,之后才会去遍历下一级节点。关于此算法的详细内容请自行查阅相关资料,本篇博客将集中在具体应用上。
  使用限定条件:最典型的是走迷宫,但说白了其实是题目要求我们探寻最短路径,或者说题目可以被简化成坐标按几种种步长移动(不局限于二维,也可能是一维),也不局限于寻路,也可以用于对某一特定条件节点的搜索,或是对这种特定坐标进行标记。但都有一个核心点,就是要连续搜索,在找到一个合法节点后需要去探知其附近的合法节点,直到这一个区域内符合合法节点的节点都被找到。
  注:以下所说的父子节点,从a坐标移动到b坐标,a节点就是父节点,b节点就是a的子节点

一.模板

本篇先以一道题的题解来说明问题

模板可以大体分成6部分
1.头文件段
2.坐标结构体段
3.障碍物预设段
4.已访问结点和移动坐标段
5.BFS算法函数段
6.主函数段

定义一个二维数组: 

int maze[5][5] = {

    0, 1, 0, 0, 0,

    0, 1, 0, 1, 0,

    0, 0, 0, 0, 0,

    0, 1, 1, 1, 0,

    0, 0, 0, 1, 0,

};

它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。
Input
一个5 × 5的二维数组,表示一个迷宫。数据保证有唯一解。
Output
左上角到右下角的最短路径,格式如样例所示。
Sample Input
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)


1.头文件段
//这里使用c++的<queue>函数,这样可以快速进行队列的操作,没啥好解释的,背下
#include<iostream>
using namespace std;
#include<stdio.h>
#include<string.h>
#include<queue>

2.坐标结构体段
//记录结点坐标,特别注意,这里的坐标也可能是一维的,不要死板,具体情况具体分析。
struct mi{
    int x;
    int y;
}ca;

3.障碍物预设段(有可能没有,是无障碍题目)
//这里往往是初始化好的迷宫地图,或是什么其他条件的障碍物,在这里1就是障碍物,
这个地图要么是自己输入,要么是题目已知条件
int map[5][5];
             ={
                {
  0,1,0,0,0},
                {
  0,1,0,1,0},
                {
  0,0,0,0,0},
                {
  0,1,1,1,0},
                {
  0,0,0,1,0},
              }   
struct mi zhen[5][5];  //这里记录着路径子节点与父节点的对应关系在5中详解

4.已访问结点和移动坐标段
//注意移动坐标要一一对应,可以使用二维数组,代表着在迷宫中怎样移动
int visited[5][5];     //用来记录已访问节点,但是也可以不要这个数组,每次走到后直接改变图,
把此节点的内容直接变成障碍物即可
int xx[4]={
  1,-1,0,0};
int yy[4]={
  0,0,-1,1};


5.BFS算法函数段
//这里主要是对BFS算法的套用,具体可以看下列详细注释
注意:凡是写到背下的,说明其基本可以完全复用,而且处于此模板的核心部分

void BFS()
{
    memset(visited,0,sizeof(visited));       //背下,初始化已访问数组
    queue<mi>q;                              //背下,初始化队列
    struct mi A;                             //背下,把第一个结点压入队列里
    A.x=0;                                   //初始化第一个节点坐标 没啥好说的
    A.y=0;                                                                                        
    visited[0][0]=1;                         //初始化首已访问节点,说明自己已被访问
    zhen[0][0].x=0;                          //初始化对应关系底层结点 下面将详细解释
    zhen[0][0].y=0;

    //特别注意:千万不要死板,此题是走迷宫,所以首节点是左上角,其他题可不一定,千万不要一堆0就上去了

    q.push(A);                              //将首节点压入队列 
    while(!q.empty())                       //背下,只要队列里还有东西就继续
    {
        struct mi te=q.front();             //这两句背下
        q.pop();

        if(te.x==4&&te.y==4)                //找到答案后退出 
            return;

        //特别注意:不一定都需要退出条件,如果题目要求我们对单节点进行移动(后面会提到)

        for(int i=0;i<4;i++)                //背下,把各个方向都试着走一遍
        {
            int zx=te.x+xx[i];              //zx,zy为移动后节点坐标
            int zy=te.y+yy[i];

            if(zx<0||zx>4||zy<0||zy>4||map[zx][zy]||visited[zx][zy])      //背下,判断是否为合法路径,比如墙和已走过节点都为非法路径,但让我前面提到过,可以把已走过节点直接在地图上变成墙也行,这样就不需要visited数组
                continue;

            visited[zx][zy]=1;              //将已访问节点标志为1 下标对应当前节点

            struct mi kao;                  //背下,将合法子节点压入队列
            kao.x=zx;
            kao.y=zy;
            q.push(kao);

            //记录着谁走到了它
            zhen[zx][zy].x=te.x;           //现在来说明这个二维数组怎样记录最短路径,首先这个数组里存的是坐标结构体,数组下标代表着子节点坐标,而数组内容存着父节点坐标,这样皆可以通过循环,一级一级找上去,既可以知道最短路径长度,也可以打印所有经过的节点坐标
            zhen[zx][zy].y=te.y;
        }
    }          
}

6.主函数部分
//略写 这没什么好说的 根据题目要求不同这个地方的灵活性也最大
int main(void)                   
{

    for(int m=0;m<5;m++)                  //初始化迷宫地图
    {
        for(int n=0;n<5;n++)
        {
            scanf("%d",&map[m][n]);
        }
    }

    BFS();            
    int num[30][2];

    int x=4,y=4;
    int i=0;
    while(1)
    {                                //把父子节点关系倒着取出放入数组中以便打印
        int k;
        k=x;
        x=zhen[x][y].x;
        y=zhen[k][y].y;

        num[i][0]=x;
        num[i][1]=y;  
        i++;
        if(x==0&&y==0)
            break;
    }

    for(int j=i-1;j>=0;j--)
    {
        printf("(%d, %d)\n",num[j][0],num[j][1]);          //打印路径节点部分
    }
    printf("(4, 4)");     
    return 0;
}

  看完这个题你可能已经了解到了这个套路的框架是什么,那么下面我将用两道题展示怎么分析,怎么套,不过这次的注释不会很详细
 
二.例题2详解部分 
1.分析

   在某知名游戏中,“闪现”是一个很有用的技能,某天你在机缘巧合之下在现实生活中也学会了这个技能,
你目前处在坐标为 a的位置上,欲到坐标为 b 的地方去。你在 1 秒钟内可以移动 1 个单位的距离,
当然也可以使用“闪现”使你目前的坐标翻倍。
输入
   输入的数据有多组,每组数据包含两个以空格为分隔符的非负整数 a 和 b。其中,0 ≤ a ≤ 1000000 ≤ b ≤100000。
输出
   输出你由 a 出发到达坐标 b 所需的最短时间,每组数据的输出占一行。
样例输入
5 17
10 20
样例输出
4
1


  分析过程:首先确定我们能不能使用此模板,一看题有一个目标坐标b,很好,再一看,需要移动坐标后再次移动,
连续移动,找到目标位置,还是属于寻路,这就非常好,已经基本确定可以使用此模板。此时不要急,先尝试简化
题目,进一步看一看题目是否符合。

  简化后题目应该是这样子,坐标轴为一维,坐标轴长度100000,你在坐标为a的点上,现在你一次有三种移动
方法,翻倍移动,前进一步或后退一步,问怎样连续移动后到达b点的时间最短。

  你这样简化后应该都笑了,因为这不就是简化版的迷宫吗?还是一维的,还只有三种移动方向,还是无障碍
地图,还问的是你最短时间(此题移动一次算一秒,故相当于问你最短移动次数),现在可以直接套了。

2.解题

#include<iostream>
using namespace std;

#include<stdio.h>
#include<string.h>
#include<queue>

struct mi{
    int x;
}ca;

void BFS(int a,int b,struct mi *zhen)
{
    int zx;
    int visited[100005];
    int xx[3]={
  0,1,-1};
    memset(visited,0,sizeof(visited));
    queue<mi>q;
    struct mi A;
    A.x=a;
    visited[a]=1;
    zhen[a].x=a;

    q.push(A);
    while(!q.empty())
    {
        struct mi te=q.front();
        q.pop();

        if(te.x==b)
            return;

        for(int i=0;i<3;i++)  //让它走3种情况
        {
            if(i==0)
                zx=te.x+te.x;
            else
                zx=te.x+xx[i];

            if(zx<0||zx>100000||visited[zx])
                continue;

            visited[zx]=1;

            struct mi kao;
            kao.x=zx;
            q.push(kao);

            zhen[zx].x=te.x;
        }
    }
}

int main(void)
{
    int a,b;
    while(scanf("%d%d",&a,&b)!=EOF)
    { 
        struct mi zhen[100005]; 

        BFS(a,b,zhen);

        int x=b;
        int i=0;
        while(x!=a)
        {
            x=zhen[x].x;
            i++;
        }

        printf("%d\n",i);
    }
    return 0;
}

//这几乎和迷宫的代码完全一致,把二维改成一维即可

三.例题3详解部分
1.分析

  你刚刚承包了一块大小为 M * N 的油田,并通过专业器具知道了哪些区块下面蕴藏着石油。
现在你想知道至少需要多少台机器才能将这块油田的所有石油采完。如果蕴藏着石油的区域如果互相
连接,那么这两块区域可以使用同一台机器。例如:若 M = 1, N = 5,其中(1, 1), (1, 2)和
(1, 4)区域有石油,那么由于(1, 1)和(1, 2)这两块区域连在一起,所以只需要两台机器即可
采完所有石油。
输入
  输入的数据有多组,每组数据首先是两个正整数 M 和 N,接下来是一个 M 行N 列的矩阵,
矩阵表示油田,矩阵中有两种可能的值,一种是“*”,表示此处没有油,一种是“@”,代表此处蕴藏
着石油。若 M, N 均为 0,则表示输入结束,该组数据 不输出任何内容 。
输出
  对于每组数据,在一行内输出需要机器的数量。
样例输入
1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0
样例输出
0
1
2
2

  分析过程:首先看到题目里有预设障碍物,而且需要搜索一个节点附近的所有合法节点,而且是属于连续
搜索,需要把每个找到的合法节点的每个方向都搜索一遍,不需要最短路径,没有目标。将所有节点搜索完成
退出。这样一看只能说应该可以用。我们再简化一下看看。
  简化题目后,应该是对于地图内的一个节点,只要与它相邻(包括斜相邻)的坐标上有合法节点,这就算
连通,也就是说只要是互相连通的节点,整个连通区域只需要一个机器,你需要找到有多少个这样的区域。
  那么怎么用呢,我们思考,它这个题的意思相当于需要我们去遍历整个地图,在每一个合法节点的周围探
知其附近有没有合法节点,并且要连续搜索,直到把搜索出的每一个合法节点的八个方向全部搜索完为止,并
且在搜索到合法节点后,将此节点的图型改成非法,以避免重复。那么就符合了我们此套路的核心--连续搜索,标记。

2.解题

#include<iostream>
using namespace std;
#include<stdio.h>
#include<string.h>
#include<queue>

struct mi{
    int x;
    int y;
}ca;

//初始障碍
char **map;

int xx[8]={
  1,-1,0,0,1,1,-1,-1};        //移动方向
int yy[8]={
  0,0,-1,1,1,-1,1,-1};


int BFS(int a,int b,int ca,int ka)
{
    if(map[a][b]=='*')                 //初始节点是非法节点不搜索
        return 0;

    queue<mi>q;
    struct mi A;
    A.x=a;
    A.y=b;

    q.push(A);
    while(!q.empty())
    {
        struct mi te=q.front();
        q.pop();

        for(int i=0;i<8;i++)  
        {
            int zx=te.x+xx[i];
            int zy=te.y+yy[i];

            if(zx<0||zx>=ca||zy<0||zy>=ka||map[zx][zy]=='*')
                continue;

            map[zx][zy]='*';          //将合法节点改为非法节点

            struct mi  kao;
            kao.x=zx;
            kao.y=zy;
            q.push(kao); 
        }
    }
    return 1;                         //说明此初始节点属于连通区域
} 

int main(void)
{
    int a,b,k,m,key,daan;
    while(1)
    { 
        daan=0;
        scanf("%d%d",&a,&b);
        getchar();

        if(a==0&b==0)
            break;

        map=(char**)malloc(a*sizeof(char*));
        for(m=0;m<a;m++)
            map[m]=(char *)malloc(b*sizeof(char));

        for(int m=0;m<a;m++)
        {
            for(int n=0;n<b;n++)
            {
                map[m][n]=getchar();
            }
            getchar();             
        }

        for(int i=0;i<a;i++)          //遍历整个地图
        {
            for(int j=0;j<b;j++)
            {
                key=BFS(i,j,a,b);
                if(key==1)
                {
                    daan++;
                }
            }
        }

        printf("%d\n",daan);

        for(int g=0;g<a;g++)
        {            
               free(map[g]);
        }
        free(map);

    }
    return 0;
}

//也没有什么特别大的改动,基本还是那个框架,只不过不需要记录路径移动坐标和长度,此题只用了搜索和标记

四.总结
  通过对以上三道算法题的探究,想必你已经初步了解到了这种模板的适用性是比较广泛的,
核心是搜索与标记,希望你能多找相关类型的的题目进行练习,算法题对于逻辑思维较差者确实
比较困难,合理记忆模板将有效帮助你解决问题。

    原文作者:jiange702
    原文地址: https://blog.csdn.net/jiange702/article/details/81365005
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。