广度优先搜索

      广度优先搜索与前面的深度优先搜索是两种特别常用图的搜索算法，广度优先搜索，是在搜索的把当前能到的点全部用队列储存起来，然后在进行队列中下一个点的搜索，知道把图搜索完成或达到了某个特定条件再结束。

看一道简单例题：给定一张地图，求里面的连通块个数

输入：在第一行中输入两个整数 r, c分别 表示地图的宽度和长度，接下来 r 行 c 列 将地图输入。

输出：在一行中输出地图的连通快个数。

看代码：

#include<stdio.h>
int book[10][10]; //记录是否搜索过
char mp[10][10]; //存储地图
struct map{ //利用结构队列存储#所在的坐标
	int x;
	int y;
};
int next[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; //利用next二维数组实现 在#点上下左右搜索
int r,c;
void bfs(int x,int y,int cnt){
	struct map queue[cnt];//将经过#的位置存储在结构队列中逐步搜索。
	int head = 0,tail = 0,i,tx,ty;
	queue[tail].x = x;
	queue[tail++].y = y;
	book[x][y] = 1;
	while (head<tail){//直到一个连通块搜索完毕再结束
		for (i=0;i<4;i++){
			tx = queue[head].x + next[i][0];
			ty = queue[head].y + next[i][1];
			if (tx<0||tx>=r||ty<0||ty>=c||book[tx][ty]==1||mp[tx][ty]=='*')
			continue;
			book[tx][ty] = 1;//记录一下该连通块搜索过了
			queue[tail].x = tx;
			queue[tail++].y = ty;
		}
		head++;
	}
	
}
int main (){
	int i,j,cnt = 0,count = 0;
	struct map maps[100];
	scanf("%d%d",&r,&c);
	for (i=0;i<r;i++)
	for (j=0;j<c;j++){
		scanf(" %c",&mp[i][j]);
		if (mp[i][j]=='#'){//记录一下地图中含有#位置的坐标
			maps[cnt].x = i;
			maps[cnt].y = j;
			cnt++; //记录含有#的个数
		}
	}
	for (i=0;i<cnt;i++){
		if (book[maps[i].x][maps[i].y]==1) //当该位置未被标记时说明这是一个新的连通块
		continue;
		count++;
		bfs(maps[i].x,maps[i].y,cnt);
	}
	printf("%d\n",count); //打印连通块个数
	
}

通过这道题可以对广度优先搜索有一个大致的了解了----利用队列 将当前位置所能到达的位置全部搜索。