广度优先搜索(BFS)


282 观看次数
1067 字数
0 评论

1:简介

我们经常会遇到一类让我们寻找目标点的问题,为了找到这个点,我们需要应用到搜索算法。

首先介绍广度优先搜索。(bfs)

什么是bfs呢?用上流的词汇介绍一下,是这样的:

广度优先搜索(Breadth First Search,BFS),简称宽搜, 又称广度优先搜索。它是从初始结点开始,应用产生式规则 和控制策略生成第一层结点,同时检查目标结点是否在这些 生成的结点中。若没有,再用产生式规则将所有第一层结点 逐一拓展,得到第二层结点,并逐一检查第二层结点是否包 含目标结点。若没有,再用产生式规则拓展第二层结点。如 此依次拓展,检查下去,直至发现目标结点为止。如果拓展 完所有结点,都没有发现目标结点,则问题无解。

咳咳咳,不会真有人能记住这个说法吧。

来,整点低端的说法。

先上一张图

我们的目标是从A点开始,搜索到目标点J。

对于广度优先搜索,搜索方式是这样的:

(1):从A开始,然后搜索第二层的B,C。

(2):搜索B的下一层D,E。

(3):搜索C的下一层F,G。(2,3合在一起搜索了整个第三层)

(4):搜索D的下一层H,I。

(5):搜索F的下一层J。(4,5合在一起搜索了整个第四层)

搜索完毕。

可以看到,在搜索J的过程中,我们把每一层的所有点都搜索过一遍(并且只走了一遍),突出了一个范围之广,所以叫他广度优先搜索。

2:例子

先来一道bfs的基础题:

Description

在一个 w×h 的矩形广场上,每一块 1×1 的地面都铺设了红色或黑色的瓷砖。小明同学站在某一块黑色的瓷砖上,他可以从此处出发,移动到上、下、左、右四个相邻的且是黑色的瓷砖上。现在,他想知道,通过重复上述移动所能经过的黑色瓷砖数。

Input

第 1 行为 h、w,2≤w、h≤50,之间由一个空格隔开;
以下为一个 w 行 h 列的二维字符矩阵,每个字符为“.”“#”“@”,分别表示该位置为黑色的瓷砖、红色的瓷砖、小明的初始位置。

Output

输出一行一个整数,表示小明从初始位置出发经过的黑色瓷砖数。

Sample Input

6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.

Sample Output

45

按照刚才的介绍,@即为起始点,目的是搜索出所有.的个数。

一个重点是如何模拟出搜索的顺序。

这里我们可以用到队列queue,储存坐标点的xy坐标。先把@的坐标入队,然后找出该点下一层的点,把@的坐标出队,下一次的点入队。之后下一次操作即为找出队列第一个点的下一层的点,把第一个点出队,它下一层的点入队................重复进行这个过程就可以完成搜索。

还需要注意的是如何寻找到某个点下一层的点。

我们可以观察一下上面的题里,@下一层的点,即@周围的点,怎么用坐标表示。

其实很简单,它四周的点分别是@的x坐标+1,x坐标-1,y坐标+1,y坐标-1。采用两个数组(或者一个二维数组)储存出改变坐标的数值,利用一个循环就可以表示出它下一层点的坐标了。差不多是这样的:

for(int i=0;i<3;i++)
{
    int x=x1+xp[i];
    int y=y1+yp[i];//xp,yp即为存储改变坐标的数组,x1,y1是原点坐标,x,y是得出的新点的坐标。
}

知道了这个,这题就很容易了。

以下是代码:

#include<bits/stdc++.h>
using namespace std;
int xp[]={1,-1,0,0};
int yp[]={0,0,1,-1};//坐标变换
int flag[103][103];//存储不能走的点的坐标。不能走的点有两种:#的点,和走过的点(上面说过了bfs的每一个点只会走一遍)
int n,m;
struct node
{
    int x,y;
}po;//储存坐标
char s[103][103];
queue<node>q;
int sum=1;//初始点也算
void rx78()
{
    while(!q.empty())
    {
        po=q.front();
        q.pop();
        int x1=po.x;
        int y1=po.y;
        for(int i=0;i<4;i++)
        {
            int x2=x1+xp[i];
            int y2=y1+yp[i];
            if(x2>=1&&x2<=n&&y2>=1&&y2<=m&&flag[x2][y2]==0)//一定要注意边界条件
            {
                sum++;
                flag[x2][y2]=1;
                q.push({x2,y2});
            }
        }
    }
}
int main()
{

    cin>>m>>n;
    for(int i=1;i<=n;i++)
        cin>>s[i]+1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(s[i][j]=='@')
            {
                q.push({i,j});//把起点入队
                flag[i][j]=1;//同时标记起点为1
            }
            if(s[i][j]=='#')
                flag[i][j]=1;
        }
    }
    rx78();
    cout<<sum<<endl;
    return 0;
}

3:bfs的优缺点

可以看出,当目标点的层次较低的时候bfs寻找到深度很小,且每个点只会查一次(这点可以类比bfs的好兄弟dfs),只要查到了就是最短的路径。

缺点是:bfs需要大量的空间来储存点的状态,需要占用大量内存。


评论区

完全没人呢

添加新评论