BFS算法

BFS算法

一、BFS的介绍

BFS（广度优先搜索，也可称宽度优先搜索）是连通图的一种遍历策略。因为它的基本思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域。

广度优先搜索（BFS）类似于二叉树的层序遍历算法，它的基本思想是：首先访问起始顶点v，然后由v出发，依次访问v的各个未被访问过的邻接顶点w1,w2,w3….wn，然后再依次访问w1，w2,…,wi的所有未被访问过的邻接顶点，再从这些访问过的顶点出发，再访问它们所有未被访问过的邻接顶点….以此类推，直到途中所有的顶点都被访问过为止。类似的想法还将应用与Dijkstra单源最短路径算法和Prim最小生成树算法。

广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点，不像深度优先搜索（DFS）那样有回退的情况，因此它不是一个递归的算法，为了实现逐层的访问，算法必须借助一个辅助队列并且以非递归的形式来实现。

二、BFS搜索的步骤

1、首先创建一个visit[ ]数组和一个队列q，分别用来判断该位置是否已经访问过及让未访问过的点入队；

2、初始化visit[ ]数组，清空q队列；

3、让起点start入队，并使该点的visit置1；

4、while（！q.empty()）{......}执行搜索操作，

a、取出队头元素后使队头元素出队，判断该元素是否为目标到达点；

b、如果是目标点，就返回结果（一般是最短时间、最短路径）；

c、如果不是目标点，就继续访问与其相邻的位置点，将可走的相邻的位置点入队，并更新visit[ ]数组；

三、BFS的应用

BFS算法一般应用于单源最短路径的搜索。

1、寻找非加权图（或者所有边权重相同）中任两点的最短路径。

2、寻找其中一个连通分支中的所有节点。（扩散性）

3、bfs染色法判断是否为二分图。

例1

Description

迷宫是一个n*m的矩阵，玩家需要迷宫入口（坐标1,1）出发，寻找路径走到出口(n,m)。请判断玩家能否从迷宫中走出，如果能走出迷宫输出，输出最短的路径长度，否则输出-1。

输入格式

第一行两个整数n和m，代表n行m列。(1<=n, m<=10)
下面n行每行m个字符,0代表可以通行，1代表不可以通行。

输出格式

如果能从迷宫走出，输出最短的路径长度，否则输出-1。

输入样例

输出样例

16

#include <iostream>
using namespace std;
char a[100][100];
int n,m,v[100][100]={0};/**< v标志数组，同时也用于记录步数 */
int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0};
void bfs(int x,int y)
{
    inti,j;/**< 两个队列qx,qy分别存储横纵坐标 */
    intqx[100005],qy[100005],fx=0,rx=0,fy=0,ry=0;
   qx[rx++]=1,qy[ry++]=1;/**<  */
    v[1][1]=1;/**<迷宫起点步数记为1 */
   while(fx!=rx)
    {
       x=qx[fx++],y=qy[fy++];
       for(i=0;i<4;i++)
        {
           int newx=x+dx[i],newy=y+dy[i];/**< bfs三要素，合法性+可访问+未标记 */
           if(newx>=1&&newx<=n&&newy>=1&&newy<=m&&a[newx][newy]=='0'&&v[newx][newy]==0)
            {
              v[newx][newy]= v[x][y]+1;/**< 因为(newx,newy)是从(x,y)走一步到达，因为步数+1 */
              qx[rx++]=newx,qy[ry++]=newy;
            }
        }
    }
}
int main()
{
   ios::sync_with_stdio(0),cin.tie(0);
    int i,j;
   cin>>n>>m;
   for(i=1;i<=n;i++)
       for(j=1;j<=m;j++)
       cin>>a[i][j];
    bfs(1,1);
   cout<<v[n][m]-1;
    return 0;
}

四、路径处理

当需要记录路径时，每生成一个子结点，就要存储指向它们父亲结点信息，此时使用的结构本质上是一个反向链式结构。以上述迷宫问题为例，定义一个数组存储(newx,newy)的父节点（x,y），反向遍历即可得到路径，反向遍历用递推实现最为容易。

全局定义一个数组 fa[100][100][2];

       x=qx[fx++],y=qy[fy++];
       for(i=0;i<4;i++)
        {
           int newx=x+dx[i],newy=y+dy[i];/**< bfs三要素，合法性+可访问+未标记 */
           if(newx>=1&&newx<=n&&newy>=1&&newy<=m&&a[newx][newy]=='0'&&v[newx][newy]==0)
            {
              v[newx][newy]= v[x][y]+1;/**< 因为(newx,newy)是从(x,y)走一步到达，因为步数+1 */
              qx[rx++]=newx,qy[ry++]=newy;
              fa[newx][newy][0]=x,fa[newx][newy][1]=y;/**< 新增语句，记录父节点 */
            }
        }

新增一个函数输出路径：

void printPath(int x,int y)
{
   if(x==0&&y==0)
       return;
   printPath(fa[x][y][0],fa[x][y][1]);/**< 先递推父节点，再输出自己 */
   cout<<x<<' '<<y<<endl;
}

例2

给定一个n × m的二维整数数组，用来表示—个迷宫，数组中只包含0或1，其中0表示可以走的路，1表示不可通过的墙壁。最初，有一个人位于左上角(1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角(n, m)处，至少需要移动多少次。

数据保证(1,1)处和(n, m)处的数字为0，且一定至少存在一条通路。

输入格式

第一行包含两个整数n和m。
接下来n行，每行包含m个整数(0或1)，表示完整的二维数组迷宫。

输出格式

输出一个整数，表示从左上角移动至右下角的最少移动次数。

数据范围

1≤n, m ≤100

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int, int>PII;
const int N = 110;
int g[N][N], d[N][N];
int n, m;
 
int bfs(){
    //初始化
       memset(d,-1, sizeof d);
       queue<PII>q;
       q.push({0,0});
       d[0][0]= 0;
       intdx[4] = {0, -1, 1, 0}, dy[4] = {1, 0, 0, -1};
       
       while(q.size()){
        //判空取头
              PIIt = q.front();
              q.pop();
        //拓展
              for(inti = 0; i < 4; i ++){
                     intx = t.first + dx[i], y = t.second + dy[i];
                     if(x>= 0 && x < n && y >= 0 && y < m &&d[x][y] == -1 && g[x][y] == 0){
                            //入队并实施相应操作。
               q.push({x, y});
                            d[x][y]= d[t.first][t.second] + 1;
                     }
              }
       }
       returnd[n - 1][m - 1];
}
int main(){
       cin>> n >> m;
       for(inti = 0; i < n; i ++){
              for(intj = 0; j < m; j ++){
                     cin>> g[i][j];
              }
       }
       cout<< bfs() << endl;
       return0;
}

例3

为了让奶牛们娱乐和锻炼，农夫约翰建造了一个美丽的池塘。这个长方形的池子被分成了 M 行 N 列个方格（1 ≤ M, N ≤ 30） 。一些格子是坚固得令人惊讶的莲花，还有一些格子是岩石，其余的只是美丽、纯净、湛蓝的水。贝西正在练习芭蕾舞，她站在一朵莲花上，想跳到另一朵莲花上去，她只能从一朵莲花跳到另一朵莲花上，既不能跳到水里，也不能跳到岩石上。贝西的舞步很像象棋中的马步：每次总是先横向移动 M1 (1 ≤ M1 ≤ 30)格，再纵向移动 M2 (1 ≤ M2 ≤ 30, M1≠M2)格，或先纵向移动 M1 格，再横向移动 M2 格。最多时，贝西会有八个移动方向可供选择。给定池塘的布局和贝西的跳跃长度，请计算贝西从起点出发，到达目的地的最小步数，我们保证输入数据中的目的地一定是可达的。

输入格式

第一行：四个用空格分开的整数：M，N，M1 和 M2第二行到 M + 1 行：第 i + 1 行有 N 个用空格分开的整数，描述了池塘第i 行的状态：0 为水，1 为莲花，2 为岩石，3 为贝西所在的起点，4 为贝西想去的终点。

输出格式

一行，从起点到终点的最少步数。

样例数据

input

4 5 1 2
1 0 1 0 1
3 0 2 0 4
0 1 2 0 0

output

2

分析

贝西的跳跃方式像马（马按“日”字形走（点击打开链接））。只要列出八个方向，判断这几个方向是否可以进行跳跃（跳跃到的位置必须有莲叶且先前没有进行过标记），如果可以则入队，不断弹出队首，直至队列为空或者跳到目标位置，跳出循环。

代码

#include<bits/stdc++.h>
using namespace std;
int m,n,m1,m2;
int a[33][33]={};
int vis[33][33]={};
int ans[33][33]={};
int lx,ly;
struct kk
{
    int x;
    int y;
} que[3333]={};
int head=1,tail=0;
int bfs()
{
   for(;head<=tail;)
    {
        intx=que[head].x;
        inty=que[head].y;//记录队首的坐标
       head++;//弹出队首
       if(x==lx&&y==ly)
        return ans[x][y];//返回答案
       if(x+m1<=m&&y+m2<=n&&vis[x+m1][y+m2]==0&&a[x+m1][y+m2]==1)
        {
           que[++tail]=(kk){x+m1,y+m2};
           vis[x+m1][y+m2]=1;
           ans[x+m1][y+m2]=ans[x][y]+1;
        }
       if(x-m1>0&&y-m2>0&&vis[x-m1][y-m2]==0&&a[x-m1][y-m2]==1)
        {
           que[++tail]=(kk){x-m1,y-m2};
           vis[x-m1][y-m2]=1;
           ans[x-m1][y-m2]=ans[x][y]+1;
        }
      if(x-m1>0&&y+m2<=n&&vis[x-m1][y+m2]==0&&a[x-m1][y+m2]==1)
        {
           que[++tail]=(kk){x-m1,y+m2};
           vis[x-m1][y+m2]=1;
           ans[x-m1][y+m2]=ans[x][y]+1;
       }
      if(x+m1<=m&&y-m2>0&&vis[x+m1][y-m2]==0&&a[x+m1][y-m2]==1)
        {
           que[++tail]=(kk){x+m1,y-m2};
           vis[x+m1][y-m2]=1;
           ans[x+m1][y-m2]=ans[x][y]+1;
        }
      if(x+m2<=m&&y+m1<=n&&vis[x+m2][y+m1]==0&&a[x+m2][y+m1]==1)
       {
              que[++tail]=(kk){x+m2,y+m1};
              vis[x+m2][y+m1]=1;
              ans[x+m2][y+m1]=ans[x][y]+1;
           }
      if(x-m2>0&&y-m1>0&&vis[x-m2][y-m1]==0&&a[x-m2][y-m1]==1)
       {
              que[++tail]=(kk){x-m2,y-m1};
               vis[x-m2][y-m1]=1;
              ans[x-m2][y-m1]=ans[x][y]+1;
           }
      if(x-m2>0&&y+m1<=n&&vis[x-m2][y+m1]==0&&a[x-m2][y+m1]==1)
       {
              que[++tail]=(kk){x-m2,y+m1};
              vis[x-m2][y+m1]=1;
              ans[x-m2][y+m1]=ans[x][y]+1;
           }
      if(x+m2<=m&&y-m1>0&&vis[x+m2][y-m1]==0&&a[x+m2][y-m1]==1)
       {
              que[++tail]=(kk){x+m2,y-m1};
              vis[x+m2][y-m1]=1;
              ans[x+m2][y-m1]=ans[x][y]+1;
           }
    }//八个方向进行跳跃
}
int main()
{
   cin>>m>>n>>m1>>m2;
    for(inti=1;i<=m;i++)
     for(intj=1;j<=n;j++)
      {
         cin>>a[i][j];
         if(a[i][j]==3)
          {
             que[++tail]=(kk){i,j};
           vis[i][j]=1;
          }//如果为初始位置，入队，并进行标记
       if(a[i][j]==4)
        {
           lx=i;
           ly=j;
           a[i][j]=1;//为了方便，这样只需要判断a[i][j]为1时可以跳跃
        } //记录结束位置
      } 
   cout<<bfs()<<endl;//bfs
    return 0;
}

例4

【奇怪的电梯】

题目描述

有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第i层楼(1<=i<=N)上有一个数字Ki(0<=Ki<=N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3 3 1 2 5代表了Ki(K1=3,K2=3,……)，从一楼开始。在一楼，按“上”可以到4楼，按“下”是不起作用的，因为没有-2楼。那么，从A楼到B楼至少要按几次按钮呢？点击打开链接

输入格式

共二行。第一行为 3 个用空格隔开的正整数，表示 N,A,B(1≤N≤200, 1≤A,B≤N)N,A,B(1≤N≤200,1≤A,B≤N) 。第二行为 N 个用空格隔开的非负整数，表示 K_i。

输出格式

一行，即最少按键次数,若无法到达，则输出 -1−1 。

样例数据

input

5 1 5
3 3 1 2 5

output

3

分析

这道题所要求的是最小值（最少要按的按钮数）。用BFS找到答案便可以退出（DFS不能保证答案为最优解）。要注意边界：是否可以继续往上或向下（没有0楼，-1楼......）。

代码

#include<bits/stdc++.h>
using namespace std;
int n,a,b;
int que[222]={};
int k[222]={};
int vis[222]={};//标记是否询问过
int tmp[222]={};
int head=1,tail=0;//队首队尾指针
void bfs(int now)
{
    
   for(;head<=tail;)//当队列不为空时
    {
        inttop=que[head];//top为队首的层数
       head++;//弹出队首
       if(top==b)
        return ;//假如已经到达了目标（b）层，直接退出
       if(top+k[top]<=n&&vis[top+k[top]]==0)//假如没有超出边界并且没有访问过
        {
           que[++tail]=top+k[top];//入队
           tmp[top+k[top]]=tmp[top]+1;//次数为上一次+1
            vis[top+k[top]]=1;//标记
        }
       if(top-k[top]>=1&&vis[top-k[top]]==0)
        {
           que[++tail]=top-k[top];
           tmp[top-k[top]]=tmp[top]+1;
           vis[top-k[top]]=1;
        }
        
    }
    return ;
}
int main()
{
   cin>>n>>a>>b;
    for(inti=1;i<=n;i++)
    cin>>k[i];
   que[++tail]=a;
    vis[a]=1;
    bfs(a);
   if(vis[b]==0)//假如没有访问过
    cout<<-1<<endl;
    else//访问过
    cout<<tmp[b]<<endl;
    return 0;
}