广度（宽度）优先搜索学习笔记-白红宇

广度（宽度）优先搜索学习笔记

阅读量：5095 次

发布时间：2019-06-13

本文共 5180 字，大约阅读时间需要 17 分钟。

广度（宽度）优先搜索学习笔记

2015-08-24 22:29:53：

宽度优先（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra算法和Prim算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

BFS，其英文全称是Breadth First Search。 BFS并不使用经验法则算法。从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的中。一般的实验里，其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中（例如或是），而被检验过的节点则被放置在被称为 closed 的容器中。（open-closed表）

以上内容摘自百度百科= =

个人见解：

DFS一条路搜到底，不到南墙不回头。BFS则为搜索周围扩展的节点然后在扩展，一般用队列实现。

基本框架：

1 Int bfs() 2  3 { 4  5 初始化，初始状态存入队列； 6  7 队列首指针head=0; 尾指针tail=1； 8  9 do10 11  {1213     指针head后移一位，指向待扩展结点；14 15     for (int i=1;i<=max;++i)                  //max为产生子结点的规则数16 17      {18 19       if (子结点符合条件)20 21          {22 23            tail指针增1，把新结点存入列尾；24 25            if (新结点与原已产生结点重复) 删去该结点（取消入队，tail减1）;26 27    else28 29        if (新结点是目标结点) 输出并退出；30 31               }32 33          }34 35 }while(head

PS：不要问窝为什么有空行，我踏马怎么知道。

TI： 细胞个数

题目描述 Description

一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如阵列:

0234500067

1034560500

2045600671

0000000089

有4个细胞。

输入描述 Input Description

【输入格式】

整数m,n

(m行，n列)矩阵

输出描述 Output Description

【输出格式】

细胞的个数。

样例输入 Sample Input

4 10

0234500067

1034560500

2045600671

0000000089

样例输出 Sample Output

数据范围及提示 Data Size & Hint

1<=m,n<=1000

思路：基本的BFS，搜索每个细胞，然后扩展该细胞上下左右，若还是细胞就入队，再搜扩展的细胞……直到搜完整个图。

程序：

1 #include
     
       2 #include
      
        3 using namespace std; 4 int dx[4]={-1,0,1,0},dy[4]={
   0,1,0,-1};  //上下左右四个方向   5 int num=0,n,m;  6 char bz[2000][2000];  7 void search(int p,int q) 8 { 9     int x,y,w,t,i;10     int h[1000][2];11     num++;//细胞数字数+1；12     bz[p][q]='0';13     t=0;14     w=1;15     h[1][1]=p; 16     h[1][2]=q;  //初始化头尾指针及队列的第一组17         do18       {19           t++;//头指针+120           for (i=0;i<=3;i++)//枚举四个方向21             {22                 x=h[t][1]+dx[i];//下一个扩展节点的坐标23                 y=h[t][2]+dy[i];24                 if ((x>=0)&&(x<10)&&(y>=0)&&(y<10)&&(bz[x][y]!='0')) //边界判断及是否为细胞数字25               {26                   w++;//尾指针+127                   bz[x][y]='0';//已搜索过28                   h[w][1]=x;29                   h[w][2]=y;//入队30               } 31             }32       } 33     while (t
       
        >bz[i][j]; //读入46     for (i=0;i<=9;i++)47       for (j=0;j<=9;j++)48         if (bz[i][j]!='0')49           search(i,j);//搜索每个细胞数字50             printf("%d",num);51     return 0; 52     fclose(stdin);53     fclose(stdout);54 }

T2：武士风度的牛

题目描述 Description

农民John有很多牛，他想交易其中一头被Don称为The Knight的牛。这头牛有一个独一无二的超能力，在农场里像Knight一样地跳（就是我们熟悉的象棋中马的走法）。虽然这头神奇的牛不能跳到树上和石头上，但是它可以在牧场上随意跳，我们把牧场用一个x，y的坐标图来表示。

这头神奇的牛像其它牛一样喜欢吃草，给你一张地图，上面标注了The Knight的开始位置，树、灌木、石头以及其它障碍的位置，除此之外还有一捆草。现在你的任务是，确定The Knight要想吃到草，至少需要跳多少次。The Knight的位置用'K'来标记，障碍的位置用'*'来标记，草的位置用'H'来标记。

这里有一个地图的例子：

　　　　　　 11 | . . . . . . . . . .

　　　　　　 10 | . . . . * . . . . .

　　　　　　 9 | . . . . . . . . . .

　　　　　　 8 | . . . * . * . . . .

　　　　　　 7 | . . . . . . . * . .

　　　　　　 6 | . . * . . * . . . H

　　　　　　 5 | * . . . . . . . . .

　　　　　　 4 | . . . * . . . * . .

　　　　　　 3 | . K . . . . . . . .

　　　　　　 2 | . . . * . . . . . *

　　　　　　 1 | . . * . . . . * . .

　　　　　　 0 ----------------------

　　　　　　　　0 1 2 3 4 5 6 7 8 9 0

The Knight 可以按照下图中的A,B,C,D...这条路径用5次跳到草的地方（有可能其它路线的长度也是5）：

　　　　　　 11 | . . . . . . . . . .

　　　　　　 10 | . . . . * . . . . .

　　　　　　 9 | . . . . . . . . . .

　　　　　　 8 | . . . * . * . . . .

　　　　　　 7 | . . . . . . . * . .

　　　　　　 6 | . . * . . * . . . F<

　　　　　　 5 | * . B . . . . . . .

　　　　　　 4 | . . . * C . . * E .

　　　　　　 3 | .>A . . . . D . . .

　　　　　　 2 | . . . * . . . . . *

　　　　　　 1 | . . * . . . . * . .

　　　　　　 0 ----------------------

　　　　　　　　0 1 2 3 4 5 6 7 8 9 0

输入描述 Input Description

第一行：两个数，表示农场的列数(<=150)和行数(<=150)

第二行..结尾: 如题目描述的图。

输出描述 Output Description

一个数，表示跳跃的最小次数。

样例输入 Sample Input

10 11

..........

....*.....

..........

...*.*....

.......*..

..*..*...H

*.........

...*...*..

.K........

...*.....*

..*....*..

样例输出 Sample Output

数据范围及提示 Data Size & Hint

Hint：这类问题可以用一个简单的先进先出表（队列）来解决。

思路：与细胞数字相同，将上下左右四个方向换为象棋中马八个方向即可，从起始位置开始搜索。

出现的错误：RE-->八个方向的数组开小了。何时该加w和t；

程序：

1 #include 
     
       2 using namespace std; 3 struct data 4 { 5     int x,y,step; 6 } 7 dl[30001]; 8 int jump2[9]={
   1,2,2,1,-1,-2,-2,-1}, 9     jump1[9]={-2,-1,1,2,2,1,-1,-2};10 int n,m,i,w,j,t,x1,x2,y1,y2,x3,y3;11 int a[200][200];12 char q;13 void bfs()14 {15     if (x1==x2&&y1==y2)16       {17           cout<<0;18           return;19       } 20     t=0;21     w=1;22     dl[t].x=x1;23     dl[t].y=y1;24     dl[t].step=0;25     while (t
      
       =1&&y3>=1&&y3<=m)32                   {33                        a[x3][y3]=1;34                        dl[w].x=x3;35                        dl[w].y=y3;36                        dl[w].step=dl[t].step+1;37                        if (dl[w].x==x2&&dl[w].y==y2)38                          {39                                cout<
       
        >m>>n;51     for (i=1;i<=n;i++)52       for (j=1;j<=m;j++)53         {54             cin>>q;55         if (q=='*') a[i][j]=1;56         if (q=='K') {x1=i;y1=j;}57         if (q=='H') {x2=i;y2=j;}58         }59     bfs();    60     return 0;61 }