breadth first search -广度优先搜索

广度优先搜索的核心：

广度优先搜索的核心是以广度为第一关键词，碰到岔路口时，总是先依次访问从该岔路口能直接到达的所有结点； 

可以理解为广度优先搜索是发散的

广度优先搜索的实现---队列

广度优先搜索的模板：

//利用队列实现广度优先搜索;
/*队列的知识复习：
1.q.pop( )是队首出队；
2.q.push( )是入队; 
3.q.front( ),q.back,分别是访问队首和队尾元素; 
*/
/*用队列实现广度优先搜索模板
void BFS(int s){queue<int > q;q.push( s);//首元素入队； while(!q.empty()){取出队首元素top;对队首元素进行操作；队首元素出队；将该结点所能到达的所有结点入队； }
}*/ 

例题一：

题目描述
给出一个mxn的矩阵，矩阵中的元素为0或1。称位置（x,y)与其上下左右四个位置(x,y+1)、(x,y-1)、（x+1,y)、(x-1,y)是相邻的。如果矩阵中有若干个1是相邻的（不必两两相邻），那么称这些1构成了一个“块”。求给定的矩阵中“块”的个数。

【输入样例】
 

6 7
0 1 1 1 0 0 1
0 0 1 0 0 0 0
0 0 0 0 1 0 0
0 0 0 1 1 1 0
1 1 1 0 1 0 0
1 1 1 1 0 0 0

【输出样例】
4

代码实现：
 

#include<iostream>
#include<queue>
using namespace std;
const int maxn=100;
struct node{int x;int y;
}Node;//Node是当前遍历到的结点; 
int n,m;
int  matrix[maxn][maxn];//matrix是矩阵的意思;
bool inq[maxn][maxn]={false};
int X[4]={0,0,1,-1};//从上往下看，对应着的是一个坐标，这个叫做增值数组; 
int Y[4]={1,-1,0,0};
bool judge(int x,int y){//判断该点是否合法，是否有被标记; if(x>=n||x<0||y>=m||y<0)return false;//越界;if(matrix[x][y]==0||inq[x][y]==true)return false;//不是1或者这个位置已经被标记了; return true; 
}
void BFS(int x,int y){queue<node> Q;Node.x=x,Node.y=y;//当前结点的坐标： Q.push(Node);inq[x][y]=true;while(!Q.empty()){node top=Q.front( );Q.pop();for(int i=0;i<4;i++){//遍历Node的四个方向; int newx=top.x+X[i];int newy=top.y+Y[i];if(judge(newx,newy)==true){Node.x=newx;Node.y=newy;Q.push(Node);//入队; inq[newx][newy]=true;//标记已经遍历过了; }}}
}
int main( ){scanf("%d%d",&n,&m);for(int x=0;x<n;x++){for(int y=0;y<m;y++){scanf("%d",&matrix[x][y]);}}int ans=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(matrix[i][j]==1&&inq[i][j]==false){ans++;BFS(i,j);//遍历这个点的四个方向，且将块内的所有1标记;  }}} printf("%d",ans);return 0;
} 
//这一题广度优先体现在，先将所在结点所能到达的所有节点先遍历后，才到下一个结点；

例题二（三维矩阵）：

PAT 甲级 1091 Acute Stroke_柘木木的博客-CSDN博客

例题三（二维矩阵，找两个点的最短距离）：

给定一个n*m大小的迷宫，其中*代表不可通过的墙壁，”.”代表平地，S代表起点，T代表终点。每次只能 上下左右移动，求S到T的最短步数。

输入样例：
 

5 5
.....
.*.*.
.*S*.
.***.
...T*
2 2 4 3

输出：

代码：
 

#include<iostream>//用广度优先搜索找矩阵内两点的最小路径; 
#include<cstring>
#include<queue>
using namespace std;
const int maxn=100;
int n,m;
int maze[maxn][maxn];
int X[4]={0,0,1,-1};
int Y[4]={1,-1,0,0}; 
bool inq[maxn][maxn]={false}; 
struct node{int x,y,step;
}Node,S,T;//结点，起点，终点; 
bool judge(int x,int y){//判断该点是否有效; if(x<0||x>=n||y<0||y>=m)return false;if(maze[x][y]=='*')return false ;if(inq[x][y]==true) return false;return true;
}
int BFS( ){queue<node> Q;Q.push(S);inq[S.x][S.y]=true;while(!Q.empty()){node top=Q.front();Q.pop();if(top.x==T.x&&top.y==T.y)return top.step;//所有的结点出队，看看有没有一个结点是终点; for(int i=0;i<4;i++){//每个结点都向四个方向蔓延,没有入过队的结点都入队; int newx=top.x+X[i];int newy=top.y+Y[i];if(judge(newx,newy)==true){ Node.x=newx;Node.y=newy;Node.step=top.step+1;//子结点的层数是父节点的层数+1，步数==层数； Q.push(Node);inq[newx][newy]=true;}}}return -1;//没有发现入队的结点有等于终点的结点； 
}
int main ( ){scanf("%d%d",&n,&m);for(int i=0;i<n;i++){getchar( );for(int j=0;j<m;j++){maze[i][j]=getchar( );}maze[i][m+1]='\0';//字符串结束标识符; }scanf("%d%d%d%d",&S.x,&S.y,&T.x,&T.y);//输入起点终点的坐标； S.step=0;//起点的层数是第0层,即最少走0步; printf("%d",BFS()); return 0;
}