【算法笔记】广度优先搜索BFS

• • 例题1
  • • 思路
    • 代码
  • 例题2
  • • 思路
    • 代码
  • 提示

void BFS(int s){
	queue q;
	q.push(s); 		//定义一个队列q，并将起点s入队
	//队列q非空
	while(!q.empty()){
		取出队首元素top;
		访问队首元素top;
		将队首元素出队;
		将top的下一层结点中未曾入队的结点全部入队，并设置为已入队; 	//标记层号为now的层号+1，同时设置这些入队的结点已入队
	}
}

给出m×n的矩阵，矩阵中的元素为0或1，称位置（x，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

枚举每一个位置的元素，如果为0，则跳过；如果为1，则使用BFS查询与该位置相邻的4个位置（前提是不出界），判断他们是否为1，如果某个相邻的位置为1，则同样去查询与该位置相邻的4个位置，直到整个1块访问完毕。为了防止走回头路，可以设置一个bool型数组inq来记录每个位置是否在BFS中已入过队。
对当前位置（x,y）来说，与其相邻的四个位，置分别为(x,y+1)，(x,y-1)，(x+1,y)，(x-1,y)，那么不妨设置下面两个增量数组，来表示四个方向：

int X[]={0,0,1,-1};
int Y[]={1,-1,0,0};

这样就可以用for循环来枚举四个方向，以确定与当前坐标(nowX,nowY)相邻的4个位置：

for(int i=0;i<4;i++){
	newX=nowX+X[i];
	newY=nowY+Y[i];
}

#include 
#include 
using namespace std;
const int maxn=100;
struct node{
	int x,y;
}Node;

int m,n;	//矩阵大小为 n×m 
int matrix[maxn][maxn];		//01矩阵 
bool inq[maxn][maxn]={false}; //记录位置x，y是否已入过队

//增量数组 
int X[]={0,0,1,-1};
int Y[]={1,-1,0,0}; 

//判断坐标x，y是否需要访问
bool judge(int x,int y){
	//越界返回false
	if(x>=n||x<0||y>=m||y<0) return false;
	//当前位置为0，或x，y已入过队，返回false
	if(matrix[x][y]==0||inq[x][y]==true) return false;
	//以上都不满足，返回true 
	return true; 
} 

//bfs函数访问位置x，y所在的块，将该块中所有1的inq都设置为true 
void BFS(int x,int y){
	queue q;
	Node.x=x,Node.y=y;	//当前结点坐标 
	q.push(Node);
	inq[x][y]=true;		//设置x，y已入过队 
	while(!q.empty()){
		node top=q.front();	//取出队首元素
		q.pop();			//队首元素出队
		//得到相邻位置 
		for(int i=0;i<4;i++){
			int newX=top.x+X[i];
			int newY=top.y+Y[i];
			//如果新的位置需要访问=true 
			if(judge(newX,newY)){
				//设置Node坐标为new
				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
		for(int y=0;y
			scanf("%d",&matrix[x][y]);	//读入01矩阵 
		}
	}
	int ans=0;	//存放块数
	//枚举每一个位置 
	for(int x=0;x
		for(int y=0;y
			//元素为1，且未入过队 
			if(matrix[x][y]==1&&inq[x][y]==false){
				ans++;	//块数加一
				BFS(x,y);	//访问整个块，将该块所有的1的inq都标记为true 
			}
		}
	} 
	printf("%dn",ans); 
	return 0;
}

给定一个n*m大小的迷宫，其中*代表不可通过的墙壁，.代表平地，S表示起点，T代表终点。当前位置是x，y，每次只能前往上下左右四个位置的平地，求从起点S到终点T的最少步数。
输入：
. . . . .
. * . * .
. * S * .
. * * * .
. . . T *
S坐标为（2，2），T坐标为（4，3）

本题求最少步数，BFS是通过层次顺序来遍历，因此可以从起点S开始计数遍历的层数，在到达终点T时的层数就是需要求解的起点S到达终点T的最少步数。

#include 
#include 
#include 
using namespace std;
const int maxn=100;
struct node{
	int x,y;
	int step;	//step为从起点S到达该位置的最少步数（层数） 
}S,T,Node;		//	S起点，T终点，Node临时结点

int n,m;	//n行，m列
char maze[maxn][maxn];	//迷宫
bool inq[maxn][maxn]={false}; 	//记录xy是否已入队 
int X[4]={0,0,1,-1};
int Y[4]={1,-1,0,0};

//检测位置x，y是否有效
bool test(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 q;
	q.push(S);	//起点S入队
	while(!q.empty()){
		node top=q.front();
		q.pop();
		//找到终点T，返回最少步数 
		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(test(newX,newY)){
				Node.x=newX,Node.y=newY;
				Node.step=top.step+1;
				q.push(Node);	//	结点入队
				inq[newX][newY]==true;	//	设置结点已入队 
			}
		}
	} 
	return -1;	//无法到达终点T时返回-1 
} 

int main(){
	scanf("%d%d",&n,&m);
	//输入迷宫 
	for(int i=0;i
		getchar();	//过滤掉每行后面的换行符 
		for(int j=0;j
			maze[i][j]=getchar();
		}
		maze[i][m+1]='';
	}
	scanf("%d%d%d%d",&S.x,&S.y,&T.x,&T.y);		// 起点和终点的坐标
	S.step=0;
	printf("%dn",BFS()); 
	return 0;
}

当使用STL的queue时，元素入队的push操作只是制造了该元素的一个副本入队，因此在入队后对原来元素的修改不会影响队列中的副本，而对队列中副本的修改也不会改变原来元素。
如：

#include 
#include 
using namespace std;
struct node{
	int data;
}a[10];
int main(){
	queue q;
	for(int i=1;i<=3;i++){
		a[i].data=i;
		q.push(a[i]);
	}
	//尝试直接把队首元素的数据域改为100
	q.front().data=100;
	printf("%d %d %dn",a[1].data,a[2].data,a[3].data);
	//尝试直接修改a[1]的数据域为200
	a[1].data=200;
	printf("%dn",q.front().data); 
	return 0;
}

所以说，当需要对队列中元素进行修改而不仅仅是访问时，队列中存放的元素最好不要是元素本身，而是他们的编号（如果是数组的话则是下标）
如：

#include 
#include 
using namespace std;
struct node{
	int data;
}a[10];
int main(){
	queue q; 	//q存放结构体数组中元素的下标 
	for(int i=1;i<=3;i++){
		a[i].data=i;	//结构体数组赋值 
		q.push(i);		//将数组下标i入队 
	}
	//把队首元素的数据域改为100
	a[q.front()].data=100;
	printf("%dn",a[1].data);
	return 0;
}