C++广度优先搜索（一）

分享目标

互联网的诞生和发展(五)

移动互联网的发展
2007年,苹果公司推出了第一代iPhone,开启了智能手机时代。智能手机的普及使得人们可以随时随
地接入互联网,移动互联网应用和服务也迅速发展。随后,谷歌推出了Android操作系统,进一步推动了移动互联网的发展。移动互联网的发展使得互联网的应用场景更加丰富,从移动支付到移动办公,从在线视频到游戏娱乐,移动互联网已经深入到人们生活的方方面面。

深度优先搜索(回顾)

深度优先搜索(Depth-First Search),简称DFS。

从一个点开始,按照一定的顺序选路,沿着某条路往下走,一直走到底(深入到底),如果走完后发现不能达到目标,返回到上一个点(回溯再试),换条路,然后继续走到底,如此往复,直至所有可能的结果都被搜索完。

广度优先搜索的概念

另一种搜索方法:
先搜索所有与A相邻的点(B、C、D),再搜索B、C、D相邻的点(E、F、G、H)。

从某一个点开始,首先探索所有与该点相邻的点,然后再进一步探索这些点的相邻点,以此类推找到目标。这种逐层递进的搜索方法,称之为广度优先搜索(Breadth-First Search),简称BFS.

搜索策略比较

深度优先搜索(DFS)

先访问起点,然后沿着一条路径深入,直到无法继续为止,再回溯到上一个分支点,继续搜索其他路径。

广度优先搜索(BFS)

从起点开始,逐层访问所有可达的节点。(先访问起点的所有邻居节点,然后访问这些邻居节点的所有邻居节点,依次类推,直到找到目标节点)

广度优先搜索过程

①当搜索顺序是“左中右”时,依次经过的点是:ABCD EFGH？

②当搜索顺序是“右中左”时,依次经过的点是:ADCBHGFE？

广度优先搜索过程

广度优先搜索同样适用于迷宫问题,例如迷宫寻宝

一个4*4的迷宫如下图所示,在方格内o表示可以走,1表示障碍物不能走,2表示宝箱,现在从(1,1)位置出发,只能“上下左右”四个方向移动,请使用广度优先搜索寻找宝箱。
具体步骤:

然后搜索这些邻居格子的所有相邻格子,依次类推(搜索过的不再搜索)

广度优先搜索过程

然后搜索这些邻居格子的所有相邻格子,依次类推

广度优先搜索的实现

广度优先搜索按照层次顺序访问节点的特点与队列的先进先出特性非常契合!所以广度优先搜索通常使用队列来实现。队列用于存储待访问的节点,确保按照层次顺序访问节点。
●初始时,出发节点入队。
● 开始处理:
①队首出队
②与队首相邻的节点依次入队(按规定的搜索顺序)
③重复以上两步直到队列为空,或者找到宝藏

定义队列和元素

1、用结构体node表示一个迷宫节点

struct node{
int x;//行
int y;//列

node s={1,1};//出发点(1,1)

};

2、定义一个存放node类型元素的队列

#include<queue> //STL队列

queue<node> q;//队列的每个元素都是一个node

队列的常用操作函数:

q.push(x)—-队尾插入元素

q.pop()—-队首删除元素

q.front()—-返回队首元素

q.back()—-返回队尾元素

q.size()—-返回元素个数

q.empty()—-队列是否为空

队列处理过程

1、初始时出发点先入队
2、开始处理
①队首出队
②与队首相邻的节点依次入队(按规定的搜索顺序)
③重复以上两步直到队列为空,或者找到宝藏

node s={1,1};

q.push (s) ;

while (! q. empty () ) {
① 队首出队
判断是否宝箱,是则结束循环,否则下一步
② 与队首相邻的节点依次入队

}

int mp[5][5];//地图,0:可通过,1:不通,2:宝藏
bool flag=false;//是否找到宝藏
node s={1,1};
q.push (s) ;
while(! q. empty () ) {
①队首出队

node cur = q.front () ;//注意,先用front()取队首,再用pop()使其出队!
q.pop ();
//判断是否有宝箱,有则结束循环,没有则下一步
if (mp[cur.x] [cur.y] == 2) {
flag = true;
break;
}
② 与队首相邻的节点依次入队
}

int mp[5][5];//地图,0:可通过,1:不通,2:宝藏
bool flag= false;//是否找到宝藏
bool visited[5][5];//标记数组
int dir[4][2]={{0,1},{1,0},{0,–1},{–1,0}};//方向数组

node s={1,1};
q. push (s) ;visited[1] [1] = true;
while (! q. empty () ) {
1 队首出队
2 与队首相邻的节点依次入队
for(int i=0;i<4;i++) {
int nx = cur.x + dir [i] [0];
int ny = cur.y + dir[i] [1];
//在地图范围内 && 没有访问过 && 可通行
if((nx>=1&&nx <= 4&&ny>=1&&ny <= 4)&& !visited [nx] [ny] && mp [nx] [ny] != 1) {
visited [nx] [ny] = true;
node next={nx,ny};
q.push (next) ;
}
}
}

//全局变量

struct node{
int x;//行
int y;//列
};
queue<node> q;
int mp[5][5];
bool flag = false;
bool visited [5] [5];
int dir[4] [2]={ ..... };
/*核心代码封装成函数bfs()*/
void bfs() {
node s={1,1}; visited[1] [1]=true; q.push(s);//出发点入队
while ( ! q. empty () ) {//队列空:搜索结束
node cur=q.front () ; q.pop();//队首出队并判断
if (mp[cur.x] [cur.y] == 2) {//找到:搜索结束
flag=true; break;
}
for(int i=0;i<4;i++) {//与队首相邻的节点依次入队：遍历四个方向（右下左上）
// 根据方向数组 dir 计算相邻格子的坐标
int nx=cur.x + dir[i] [0];
int ny=cur.y + dir[i] [1];
if((nx>=1&&nx <= 4&&ny>=1&&ny <= 4)&& !visited [nx] [ny]&& mp [nx] [ny] != 1) {
visited[nx] [ny]=true;
node next={nx, ny} ;
q. push (next) ;
}
}
}
}

搜索结束方式:
1 队列空
2 找到宝藏

广度优先搜索的实现(完整代码)

一个4*4的迷宫如下图所示,在方格内o表示可以走,1表示障碍物不能走,2表示宝箱,现在从(1,1)位置出发,只能“上下左右”四个方向移动,请实现广度优先搜索寻找宝箱。找到输出“YES”,否则输出“NO”。

void bfs(){
node s={1,1};
visited [1] [1] = true;
q.push (s) ;
while(!q. empty () ) {
node cur = q.front () ;
q.pop () ;
if (mp [cur.x] [cur.y] == 2) {
flag = true; break;
}
for(int i = 0;i<4;i++) {
int nx = cur.x + dir[i] [0] ;
int ny = cur. y + dir[i] [1] ;
//在地图范围内 && 没有访问过 && 可通行
if((nx>=1 && nx <= 4 && ny>=1 && ny <= 4) && !visited [nx] [ny] && mp [nx] [ny] != 1) {
visited [nx] [ny] = true;
node next={nx,ny};
q.push (next) ;
}
}
}
}
int main(){
for(int i=1;i <= 4;i++) {
for(int j=1;j <= 4;j++) {
cin >> mp[i][j];
}
}

bfs();
if (flag)cout << "YES";
elsecout << "NO";
return 0;
}

应用场景

广度优先搜索(BFS)可应用于:

迷宫寻宝

已知山洞里面是由许多房间组成的迷宫,每个房间可以通往上下左右四个房间,迷宫大小是一个NN的正方形,其中有一些怪兽堵路。现在从起始(1,1)的位置进入洞穴寻找宝藏(已有一个宝箱),如果可以找到宝藏输出YES,否则输出NO。要求用广度优先搜索实现。
【输入格式】第一行是一个正整数N(2<N≤10),后面包含NN行,由‘.’、‘’、‘#’组成的矩阵,其中’表示可以走,‘’表示怪兽,‘#’表示宝藏的位置。
【输出格式】找到宝藏输出YES,否则输出NO。

读题可知,本题是迷宫连通性问题,即求解从出发点(1,1)是否能到达宝藏点。与前面4*4迷宫寻宝问题的差别:

//全局变量

struct node{
int x;//行
int y;//列
};
queue<node> q;
char mp[11][11];
bool flag = false;
bool visited [11] [11];
int dir[4] [2]={ ..... };
/*核心代码封装成函数bfs()*/
void bfs() {
node s={1,1}; visited[1] [1]=true; q.push(s);//出发点入队
while ( ! q. empty () ) {//队列空:搜索结束
node cur=q.front () ; q.pop();//队首出队并判断
if (mp[cur.x] [cur.y] == '#') {//找到:搜索结束—–更新宝藏判断条件
flag=true; break;
}
for(int i=0;i<4;i++) {//与队首相邻的节点依次入队：遍历四个方向（右下左上）
// 根据方向数组 dir 计算相邻格子的坐标
int nx=cur.x + dir[i] [0];
int ny=cur.y + dir[i] [1];
if((nx>=1&&nx <= n &&ny>=1&&ny <= n)&& !visited [nx] [ny]&& mp [nx] [ny] != '*') {//—–更新地图范围判断、更新可通行判断
visited[nx] [ny]=true;
node next={nx, ny} ;
q. push (next) ;
}
}
}
}

修改4*4迷宫寻宝问题main函数

//添加全局变量n
int n;

int main() {
cin >> n;

char t[11];
for(int i=1;i <= n;i++) {
cin >> t;
for(int j=0;j<n; j++)//输入地图信息。行内字符间没有空格隔开,需要处理。
mp[i] [j+1] = t[j];
}
if (mp[1] [1] != '*')//先判断出发点可通行
bfs();
if(flag) cout << "YES";
else cout << "NO";
return 0;
}

完整代码

#include<iostream>
using namespace std;

//全局变量

struct node{
int x;//行
int y;//列
};
queue<node> q;
int n;
char mp[11][11];
bool flag = false;
bool visited [11] [11];
int dir[4] [2]={ ..... };
/*核心代码封装成函数bfs()*/
void bfs() {
node s={1,1}; visited[1] [1]=true; q.push(s);//出发点入队
while ( ! q. empty () ) {//队列空:搜索结束
node cur=q.front () ; q.pop();//队首出队并判断
if (mp[cur.x] [cur.y] == '#') {//找到:搜索结束—–更新宝藏判断条件
flag=true; break;
}
for(int i=0;i<4;i++) {//与队首相邻的节点依次入队：遍历四个方向（右下左上）
// 根据方向数组 dir 计算相邻格子的坐标
int nx=cur.x + dir[i] [0];
int ny=cur.y + dir[i] [1];
if((nx>=1&&nx <= n &&ny>=1&&ny <= n)&& !visited [nx] [ny]&& mp [nx] [ny] != '*') {//—–更新地图范围判断、更新可通行判断
visited[nx] [ny]=true;
node next={nx, ny} ;
q. push (next) ;
}
}
}
}
int main() {
cin >> n;

char t[11];
for(int i=1;i <= n;i++) {
cin >> t;
for(int j=0;j<n; j++)//输入地图信息。行内字符间没有空格隔开,需要处理。
mp[i] [j+1] = t[j];
}
if (mp[1] [1] != '*')//先判断出发点可通行
bfs();
if(flag) cout << "YES";
else cout << "NO";
return 0;
}

n*n迷宫寻宝的区FS模版代码

MAXN:n的最大值+1

struct node{
int x;//行
int y;//列
};
queue<node> q;
int n;
char mp[MAXN][MAXN];
bool flag = false;
bool visited [MAXN] [MAXN];
int dir[4] [2]={ ..... };

void bfs() {
node s={1,1}; visited[1] [1]=true; q.push(s);//出发点入队
while ( ! q. empty () ) {//队列空:搜索结束
node cur=q.front () ; q.pop();//队首出队并判断
if (mp[cur.x] [cur.y] == '#') {//找到:搜索结束—–更新宝藏判断条件
flag=true; break;
}
for(int i=0;i<4;i++) {//与队首相邻的节点依次入队：遍历四个方向（右下左上）
// 根据方向数组 dir 计算相邻格子的坐标
int nx=cur.x + dir[i] [0];
int ny=cur.y + dir[i] [1];
if((nx>=1&&nx <= n &&ny>=1&&ny <= n)&& !visited [nx] [ny]&& mp [nx] [ny] != '*') {//—–更新地图范围判断、更新可通行判断
visited[nx] [ny]=true;
node next={nx, ny} ;
q. push (next) ;
}
}
}
}

时间复杂度O(n^2)
空间复杂度O(n^2)

红与黑

有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上,只能向上下左右四个方向的相邻的黑色瓷砖移动。请写一个程序,计算你总共能够到达多少块黑色的瓷砖。要求用广度优先搜索实现。
【输入描述】
第一行是两个整数W和H,分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中,每行包括W个字符。每个字符表示一块瓷砖的颜色,规则如下
1)‘:黑色的瓷砖;
2)‘#’:红色的瓷砖;
3)‘@’:黑色的瓷砖,并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。
【输出描述】输出一行,显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

【输入样例】
m n
6 9分别表示x方向和y方向瓷砖的数量
....#.
.....#
......
......
......
......
......

#@ ... #
.# .. #.

【输出样例】
45
即9行6列,对应迷宫大小是9*6。
读入信息时转换一下,变成我们习惯的方式n行m列:
(即先读入的数是m,后读入n)

1)':黑色的瓷砖;
>2)‘#':红色的瓷砖;
3)‘@':黑色的瓷砖,并且你站在这块瓷砖上。

'、‘@'可通行

n = 9, m=6

读题可知,本题是连通块格子数量问题,即求解出发点所在的连通块内有多少格子。

#define MAXN 21
int n,m;//n行m列的迷宫
int sx,sy;//出发点行列信息
int cnt;//格子数

#include<iostream>
using namespace std;
struct node{
int x;//行
int y;//列
};
queue<node> q;
#define MAXN 21
int n,m;//n行m列的迷宫
int sx,sy;//出发点行列信息

char mp [MAXN] [MAXN];
bool flag = false;
bool visited [MAXN] [MAXN] ;
int dir [4] [2]={{0,1},{1,0},{0,–1},{–1,0}};
int cnt;//格子数
void bfs(){
node s={sx,sy};
visited [sx][sy]=true;
cnt++;
q.push (s) ;
while(! q. empty () ) {
node cur=q.front ();
q.pop();//无需判断终点
for(int i=0;i<4;i++) {
int nx=cur.x + dir[i] [0];
int ny=cur. y + dir [i] [1];
if((nx>=1&&nx <= n&&ny>=1&&ny <= m&& !visited [nx] [ny] && mp [nx] [ny] ! = ' #' ) {//通行条件:非红瓷砖
visited[nx][ny]=true;
cnt++;
node nexc (nA/ny]
q.push (next) ;
}
}
}
}

int main() {
cin >>m >>n;//注意:m先,n后,n行m列的迷宫
char t [MAXN];
for(int i=1;i <= n;i++) {
cin >>t;//行内字符间没有空格隔开,需要处理
for(int j=0;j<m; j++) {
if(t[j] == '@'){//记录出发点位置
sx=i;
sy=j+1;
}
mp[i] [j+1]=t[j];
}
}
bfs();
cout << cnt;
return 0;
}

连通块格子数的区FS模版代码

水洼个数

有一块N×M的土地,雨后积起了水,有水标记为‘W’,干燥为‘’。八连通的积水被认为是连接在一起的。请求出院子里共有多少水洼?要求用广度优先搜索实现。
【输入描述】第一行为N,M(1≤N、M≤100)。后面为N行,每行M个字符,表示这行的土地状况。
【输出描述】一行,共有的水洼数。

读题可知,本题是连通块数量问题,即地图中总共有多少连通块。

迷宫连通块统计的思路:

完整代码

#include<iostream>
#include<queue>
using namespace std;

struct node{
int x; //行
int y; //1
};
queue<node> q;
#define MAXN 101 //n,m的最大值+1
int n,m;
int sx, sy;
char mp[MAXN][MAXN];//地图,有水为‘W',干燥为‘.’
bool visited [MAXN] [MAXN];
int dir[8][2]={{–1,1},{0,1},{1,1},{1,0},{1,–1},{0,–1},{–1,–1},{–1,0}};//8方向的方向
int cnt; //连通块数量

void bfs() {
node s={sx, sy} ;
visited [sx] [sy] = true;
cnt++;
q.push (s) ;
while(!q. empty () ) {
node cur = q.front () ;
q.pop() ;
for(int i=0;i<8;i++) {
int nx = cur. x + dir[i] [0] ;
int ny = cur.y + dir[i] [1] ;
//在地图范围内 && 没有访问过 && 可通行
if((nx>=1 && nx <= n && ny>=1 && ny <= m) && !visited [nx] [ny] && mp [nx] [ny] != '.'){
visited [nx] [ny] = true;
node next={nx,ny};
q.push (next) ;
}
}
}
}
int main(){
cin >>n>>m;// n行m列的迷宫
char t [MAXN];
for(int i=1;i <= n;i++) {
cin >>t;//行内字符间没有空格隔开,需要处理
for(int j=0;j<m;j++) {
mp[i] [j+1] = t[j];
}
}

for(int i=1;i <= n;i++) {
for(int j=1;j <= m;j++) {
if(!visited [i] [j] && mp[i] [j] == 'w' ){
sx=i;
sy=j;
bfs();//以(sx,sy)为起点搜索
}
}
}
cout << cnt;
return 0;
}

本次分享的知识点

1、关于广度优先搜索(BFS)的基本思想,说法正确的是?B

A、从起始节点开始,沿着一条路径一直走到底,直到无法再走下去为止,然后回溯到上一个节点
B、从起始节点开始,依次遍历当前节点的所有邻居节点,然后再依次遍历邻居节点的所有邻居节点
C、从起始节点开始,随机选择一个邻居节点进行访问
D、从起始节点开始,优先访问距离最远的节点
2、根据广度优先搜索思想,下图按照先左后右的顺序从1号开始搜索,搜索的路径是?(搜索过的点不再统计)C
A、1-2-5-4-3-6-7-8

B、1-2-3-4-5-6-8-7

C、1-2-3-4-5-6-7-8

D、1-2-4-5-3-7-6-8

能养几只公羊

有一个农夫有个nxm大小的农场,农场的四周有墙把农场跟外面隔离开,同时农场里也有一些隔离墙,其余的是空地。农夫想养一些公羊,但是公羊好斗,而且公羊在农场里会“上下左右”四处走动(但不能穿过墙),两只公羊不能见面(见面就会顶角受伤)。为了不让公羊受伤,农夫想知道他的农场最多能养几只公羊?为了方便起见,农场的描述用0表示空地,1表示墙。
【输入格式】第一行输入n和m,表示农场大小是nxm(1≤n,m≤1000)。接下来是一个nxm的矩阵,矩阵里每个值是0或者1。行内数之间用空格隔开。
【输出格式】一行,一个整数,表示农夫能养的公羊数量。

【输入样例】

4 5

1 0 1 1 1

1 0 1 0 1

1 1 1 1 0

1 0 0 0 0

【输出样例】

3
【分析】
· 一个连通块内只能养一只公羊。连通块数量就是能养的公羊数量。
· 这是一个求四向迷宫连通块数量的问题。
· 可以用深度优先搜索,也可以用广度优先搜索实现。

#include<iostream>
#include<queue>
using namespace std;

struct node{
int x; //行
int y; //1
};
queue<node> q;
#define MAXN 1001//n,m的最大值+1
int n,m;
int sx, sy;
int mp[MAXN][MAXN];//地图,0表示空地,1表示墙
bool visited [MAXN] [MAXN];
int dir [4] [2]={{0,1},{1,0},{0,–1},{–1,0}};//TÆE
int cnt;//连通块数量

void bfs() {
node s={sx,sy} ;
visited [sx] [sy] = true;
cnt++;
q.push (s) ;
while (!q. empty () ) {
node cur = q.front () ;
q.pop () ;
for(int i=0;i<4;i++) {
int nx = cur.x + dir[i] [0] ;
int ny = cur.y + dir[i] [1] ;
//在地图范围内 && 没有访问过 && 可通行
if((nx>=1 && nx <= n && ny>=1 && ny <= m) && !visited [nx] [ny] && mp [nx] [ny] != 1) {
visited [nx] [ny] = true;
node next={nx,ny};
q.push (next) ;
}
}
}
}
int main(){
cin >>n>>m;//n行m列的迷宫
for(int i=1;i <= n;i++) {
for(int j=1;j <= m;j++) {
cin >> mp[i][j];
}
}
for(int i=1;i <= n;i++) {
for(int j=1;j <= m;j++) {
if(!visited[i] [j] && mp[i][j] == 0 ){
sx=i;
sy=j;
bfs();//以(sx,sy)为起点搜索
}
}
}
cout << cnt;
return 0;
}