【算法基础】广度优先搜索算法

博主： Fivk
发布时间：2021 年 08 月 24 日
1435 次浏览
暂无评论
5044字数
分类：算法基础

搜索是计算机程序设计中一种最基本、最常用的算法。搜索算法是直接基于计算机高速运算的特点而使用的计算机求解方法。
它是从问题的初始状态出发，根据其中的约束条件，按照一定的策略，有序推进，不断深入，对于达到的所有目标状态（解空间），一一验证，找到符合条件的解（可行解），或者找出所有可行解中的最优解。
按照推进的控制策略，搜索一般分为宽度优先搜索和深度优先搜索。

# 一、广度优先搜索算法过程

广度优先搜索算法（又称宽度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。
广度优先算法的核心思想是：从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点。若没有，再用算符逐一扩展第二层的所有节点……，如此依次扩展，检查下去，直到发现目标节点为止。即

1. 从图中的某一顶点V0开始，先访问V0；
2. 访问所有与V0相邻接的顶点V1，V2，......，Vt；
3. 依次访问与V1，V2，......，Vt相邻接的所有未曾访问过的顶点；
4. 循此以往，直至所有的顶点都被访问过为止。

这种搜索的次序体现沿层次向横向扩展的趋势，所以称之为广度优先搜索。

# 二、广度优先算法描述

```cpp
int bfs()
{
    初始化，初始化状态存入队列
  
    while(!que.empty())		// 队列不为空
    {
        指针 head 后移一位，指向待扩展结点;
	for(int i = 1; i <= max; i++)		//max 为产生子结点的规模数
	{
	    if(子结点符合条件)
	    {
		que.push(符合条件的子结点);
		if(新结点与原已产生结点重复) 删去该节点（取消入队）;
		else
		    if(新节点是目标结点) 输出并退出;
	    }
	}
	// 下一个点 继续搜索
	que.pop();
     } 
}
```

> **【算法思想】**
>
> 假设你经营着一个芒果农场,需要寻找芒果销售商，以便将芒果卖给他。在社交平台上，你与芒果销售商没有直接联系，为此，你可在朋友中查找。
>
> ![](https://blog.fivk.cn/usr/uploads/2021/08/3534486387.png)
>
> 这种查找很简单。首先，创建一个朋友名单。
>
> ![](https://blog.fivk.cn/usr/uploads/2021/08/2946865068.png)
>
> 然后，依次检查名单中的每个人，看看他是否是芒果销售商。
>
> ![](https://blog.fivk.cn/usr/uploads/2021/08/1861197369.png)
>
> 假设你没有朋友是芒果销售商，那么你就必须在朋友的朋友中查找。
>
> ![](https://blog.fivk.cn/usr/uploads/2021/08/905354054.png)
>
> 检查名单中的每个人时，你都将其朋友加入名单。如果你的朋友有共同的朋友，则名单只需被添加一次。
>
> ![](https://blog.fivk.cn/usr/uploads/2021/08/2384963159.png)

# 三、广度优先搜索注意事项

1. 每生成一个子节点，就要提供指向它们父节点的指针。当解出现时候，通过逆向跟踪，找到从根结点到目标结点的一条路径。当然不要求输出路径，就没必要记父亲节点。
2. 生成的结点要与前面所有已经产生的结点比较，以免出现重复结点，浪费时间和空间，还有可能陷入死循环。
3. 如果目标节点的深度与“费用”（比如长度）成正比，那么，找到第一个解即为最优解，这时，这时搜索速度比深度搜索要快些，在求最优解时往往采用广度优先搜索；如果结点的“费用”不与深度成正比时，第一次找的解不一定时最优解。
4. 广度优先搜索的效率还有赖于目标节点所在的位置情况，如果目标结点深度处于较深层时，需要搜索的结点数基本上以指数增长。

# 四、经典例题

### 例题 1 解救A同学

> 迷宫由n行m列的单元格组成（n和m都小于等于50），每个单元格要么是空地，要么是障碍物。你的任务是找到一条从迷宫的起点通往A同学所在位置的最短路径，最终需要几步。注意障碍物是不能走的，当然也不能走到迷宫之外。

![](https://blog.fivk.cn/usr/uploads/2021/08/2111580759.png)

第一行有两个数n，m。n表示迷宫的行，m表示迷宫的列。接下来n行m列为迷宫，0表示空地，1表示障碍物。最后一行4个数，前两个数为迷宫入口的x和y坐标。后两个为小哈的x和y坐标。

```in
4 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
1 1 4 3
```

运行结果

```out
7
```

我们用一个二维数组来存储这个迷宫。最开始的时候我们在迷宫（1,1）处，可以往右走或者往下走。“一层一层”扩展的方法来找到A同学。扩展时每发现一个点就将这个点加入到队列中，直至走到A同学的位置(p,q)时为止，具体如下。
最开始我们在入口（1,1）处， 一步之内可以到达的点有（ 1,2）和（2,1）。

![](https://blog.fivk.cn/usr/uploads/2021/08/3528742331.png)

但是A同学并不在这两个点上， 那我们只能通过（1，2）和（2，1）这两点继续往下走。比如现在走到了（1,2）这个点，之后又能够到达哪些新的点呢？有（2,2）。再看看通过（2,1 ）又可以到达哪些点呢？可以到达（2，2）和（3，1）。 此时你会发现（2，2）这个点既可以从（ 1，2）到达， 也可以从（ 2，1）到达， 并且都只使用了2 步。为了防止一个点多次被走到， 这里需要一个数组来记录一个点是否己经被走到过。

![](https://blog.fivk.cn/usr/uploads/2021/08/3543578339.png)

此时2步可以走到的就全走到了，有（2，2）和（3，1），可是A同学并不在这两个点上，没有别的方法，还得继续往下尝试，看看通过（2，2）和（3，1）这两个点还能到达哪些新的没有走到过的点。通过（2，2）这个点我们可以到达（2，3）和（3，2），通过（3，1）可以到达（3，2）和（4，1）。现在第3步可以到达的点有（2，3）、（3，2）和（4，1）依旧没有到达A同学的所在点，我们需要重复刚才的方法，直到到达A同学所在点为止。

![](https://blog.fivk.cn/usr/uploads/2021/08/3989367587.png)

```cpp
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

// 创建一个结构体
struct Node{
    int x;
    int y;
    int step;   // 到达当前点的最小步数
};

int a[101][101];    // 用于存储迷宫的原始数据
bool b[101][101];   // 用于标记点 x y 是否被访问过

int n,m;
int start_x, start_y, end_x, end_y;  // 起点坐标与终点坐标
bool flag = false;  // 假定不能到达终点
int np[4][2] = {
    {0,1},  // 向右
    {1,0},  // 向下
    {0,-1}, // 向左
    {-1,0}  // 向左
};

queue<Node> que;
void dfs();

int main()
{
    cin >> n >> m;

// 初始化迷宫
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> a[i][j];
    // 输入起点坐标和终点坐标
     cin >> start_x >> start_y >> end_x >> end_y;

// 搜索
    dfs();

if(flag)
        cout << que.back().step << endl;
    else
        cout << -1 <<endl;

system("pause");
    return 0;
}

void dfs()
{
    // 起点入队 并 标记(标记后不能被访问了)
    Node startnode;
    startnode.x = start_x;
    startnode.y = start_y;
    startnode.step = 0;     // 初始 (1,1) 位置步数为 0

b[start_x][start_y] = true; // 标记起点
    que.push(startnode);

while(!que.empty())
    {
        // 当 que 不为空，我们扩展四个方向
        for(int i = 0; i < 4; i++)
        {
            // 四个方向 和 搜索与回溯一样
            int nx = que.front().x + np[i][0];
            int ny = que.front().y + np[i][1];

// 判断得到的这个方向是否可用
            // 条件 ： 不能越界、不能是墙、不能被访问过(没有如过队)
            if(nx >= 1 && nx <= n && ny >= 1 && ny <=n && !a[nx][ny] && !b[nx][ny])
            {
                b[nx][ny] = true;
                Node newnode;
                newnode.x = nx;
                newnode.y = ny;
                newnode.step = que.front().step + 1;
                que.push(newnode);
            }

// 检测是否到达终点
            if(nx == end_x && ny == end_y)
            {
                flag = true;    // 表示找到了 A 同学
                return;
            }
        }
        // 当前队首4个方向没有找到，把自己出队
        que.pop();
    }
}
```

### 例题 2 交通图

> 如下图表示的是从城市A到城市H的交通图。从图中可以看出，从城市A到城市H要经过若干个城市。相邻城市之间距离为1，现要找出一条经过城市最少的一条路线。（H-F-A）

![](https://blog.fivk.cn/usr/uploads/2021/08/787576822.png)

【算法分析】
看到这图很容易想到用邻接距阵来表示，0表示能走，1表示不能走。

![](https://blog.fivk.cn/usr/uploads/2021/08/3958980229.png)

```cpp
int  map[9][9] = { 
   {0,0,0,0,0,0,0,0,0},
   {0,1,0,0,0,1,0,1,1},
   {0,0,1,1,1,1,0,1,1},
   {0,0,1,1,0,0,1,1,1},
   {0,0,1,0,1,1,1,0,1},
   {0,1,1,0,1,1,1,0,0},
   {0,0,0,1,1,1,1,1,0},
   {0,1,1,1,0,0,1,1,0},
   {0,1,1,1,1,0,0,0,1} 
};
```

首先想到的是用队列的思想。que是存储扩展结点的队列， 记录经过的城市，pre[i] 记录前驱城市，这样就可以倒推出最短路线。具体过程如下：

- (1) 将城市A入队，即将第一个结点初始化为1.
- (2) 将队首所指向的城市所有可直通的城市入队（如果这个城市在队列中出现过就不加入队，可用一布尔数组b[i] 来判断），将入队城市的前趋城市保存在b[i] 中。然后将队首加1，得到新的队首城市。重复以上步骤，直到搜到城市 H 时，搜索结束。利用b[i] 可倒推出最少城市线路。

```cpp
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

void bfs();

//  结点数 1-8 表示 A-H
int  map[9][9] = { 
   {0,0,0,0,0,0,0,0,0},
   {0,1,0,0,0,1,0,1,1},
   {0,0,1,1,1,1,0,1,1},
   {0,0,1,1,0,0,1,1,1},
   {0,0,1,0,1,1,1,0,1},
   {0,1,1,0,1,1,1,0,0},
   {0,0,0,1,1,1,1,1,0},
   {0,1,1,1,0,0,1,1,0},
   {0,1,1,1,1,0,0,0,1} 
};

bool b[101];    //判断是否被访问过
int pre[101];   // 保存前趋结点

queue<int> que;

int main()
{
    bfs();
    int k = 8;
    cout << char(k+64);
    while(pre[k])
    {
        cout << '-' << char(pre[k]+64);
        k = pre[k];
    }
    cout << endl;
    system("pause");
}

void bfs()
{
    que.push(1);
    b[1] = true;
    while(!que.empty())
    {
        int cur = que.front();  // 获取队首结点
        for(int i = 1; i <= 8; i++)     // 遍历与队首相连的点
        {
            if(map[cur][i] == 0 && !b[i])
            {
                b[i] = true;
                que.push(i);
                pre[i] = cur;
                if(i == 8)  return; // 第一次搜索到 H 城市时路线最短
                                    // 广度优先搜索注意事项 第3点
            }
        }
        que.pop();
    }
}
```

### 例题3 细胞

> 一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。
>
> 【输入】
> 第一行为矩阵的行n和列m;
> 下面为一个n×m的矩阵。
> 1<=n,m<=100
>
> 【输出】
> 细胞个数。
>
> 【输入样例】
>
> ```in
> 4 10
> 0234500067
> 1034560500
> 2045600671
> 0000000089
> ```
>
> 【输出样例】
>
> ```out
> 4
> ```

- (1)  输入m*n矩阵，将其转化为 boolean 矩阵存入bz数组中；
- (2)  沿 bz 数组矩阵从上到下、从左到右，找到遇到的第一个细胞；
- (3) 将细胞的位置入队 h，并沿其上、下、左、右四个方向的细胞入队，入队后的位置 bz 数组置为false；
- (4) 将 h 队的队头出队，沿其上、下、左、右四个方向的细胞位置入队，入队后的位置 bz 数组置为 false；
- (5) 重复 (4) ，直至 h 队空为止，此时找到了一个细胞；
- (6) 重复  (2) ，直至矩阵找不到细胞；
- (7) 输出找到的细胞数。

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

void bfs(int x,int y);

// 位移量
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};

// 入队信息
struct Node
{
    int x;
    int y;
};

int count = 0;          // 统计细胞个数
int n,m;
char s[101];
int b[101][101];

int main()
{
    cin >> n >> m;
    getchar();  // 读取 \n

for(int i = 0; i < n; i++)
    {
        cin.getline(s,101);
        for(int j = 0; j < m; j++)
        {
            if(s[j]!='0')
                b[i][j] = 1;
        }
    }

for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(b[i][j] == 1)
                bfs(i,j);
        }
    }

cout << count << endl;
    system("pause");
    return 0;
}

void bfs(int x,int y)
{
    queue<Node> que;
    Node Data;
    Data.x = x; 
    Data.y = y;
    b[x][y] = 0;
    que.push(Data);
    count++;

while(!que.empty())
    {
        for(int i = 0; i < 4; i++)
        {
            int nx = que.front().x + dx[i];
            int ny = que.front().y + dy[i];
            if(nx >= 0 && nx < n && ny >= 0 && ny < m && b[nx][ny] == 1)
            {
                b[nx][ny] = 0;
                Data.x = nx;
                Data.y = ny;
                que.push(Data);
            }
        }
        que.pop();
    }
    return;
}
```

最后修改：2021 年 09 月 12 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

本当迷
哈哈时过境迁再看一遍帆的文章质量还是那么高
挺胸的打工人
感谢博主分享
菜菜
一天就学一些我不知道的东西(´இ皿இ｀)
zhanqy
博主赛高！
null ？？［］
还可以把扩展运算符加上呀，这个很有用［…arr］，用于数组合...

【算法基础】广度优先搜索算法

Fivk • 2021 年 08 月 24 日

# 一、广度优先搜索算法过程

这种搜索的次序体现沿层次向横向扩展的趋势，所以称之为广度优先搜索。

# 二、广度优先算法描述

# 三、广度优先搜索注意事项

# 四、经典例题

### 例题 1 解救A同学

![](https://blog.fivk.cn/usr/uploads/2021/08/2111580759.png)

```in
4 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
1 1 4 3
```

运行结果

```out
7
```

![](https://blog.fivk.cn/usr/uploads/2021/08/3528742331.png)

![](https://blog.fivk.cn/usr/uploads/2021/08/3543578339.png)

![](https://blog.fivk.cn/usr/uploads/2021/08/3989367587.png)

```cpp
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

// 创建一个结构体
struct Node{
    int x;
    int y;
    int step;   // 到达当前点的最小步数
};

int a[101][101];    // 用于存储迷宫的原始数据
bool b[101][101];   // 用于标记点 x y 是否被访问过

queue<Node> que;
void dfs();

int main()
{
    cin >> n >> m;

// 搜索
    dfs();

if(flag)
        cout << que.back().step << endl;
    else
        cout << -1 <<endl;

system("pause");
    return 0;
}

b[start_x][start_y] = true; // 标记起点
    que.push(startnode);

### 例题 2 交通图

![](https://blog.fivk.cn/usr/uploads/2021/08/787576822.png)

【算法分析】
看到这图很容易想到用邻接距阵来表示，0表示能走，1表示不能走。

![](https://blog.fivk.cn/usr/uploads/2021/08/3958980229.png)

首先想到的是用队列的思想。que是存储扩展结点的队列， 记录经过的城市，pre[i] 记录前驱城市，这样就可以倒推出最短路线。具体过程如下：

```cpp
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

void bfs();

bool b[101];    //判断是否被访问过
int pre[101];   // 保存前趋结点

queue<int> que;

int main()
{
    bfs();
    int k = 8;
    cout << char(k+64);
    while(pre[k])
    {
        cout << '-' << char(pre[k]+64);
        k = pre[k];
    }
    cout << endl;
    system("pause");
}

### 例题3 细胞

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

void bfs(int x,int y);

// 位移量
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};

// 入队信息
struct Node
{
    int x;
    int y;
};

int count = 0;          // 统计细胞个数
int n,m;
char s[101];
int b[101][101];

int main()
{
    cin >> n >> m;
    getchar();  // 读取 \n

for(int i = 0; i < n; i++)
    {
        cin.getline(s,101);
        for(int j = 0; j < m; j++)
        {
            if(s[j]!='0')
                b[i][j] = 1;
        }
    }

for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(b[i][j] == 1)
                bfs(i,j);
        }
    }

cout << count << endl;
    system("pause");
    return 0;
}

void bfs(int x,int y)
{
    queue<Node> que;
    Node Data;
    Data.x = x; 
    Data.y = y;
    b[x][y] = 0;
    que.push(Data);
    count++;

【算法基础】广度优先搜索算法

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【踩坑日志】SpringBoot项目启动提示This primary key of "id" is primitive !不建议如此请使用包装类 in Class:

【C】极域电子教室学生端解除控制

【开发技巧】@CrossOrigin注解解决跨域问题

【Fivk】文章归档

回忆刚入天柱二中的我

【Linux笔记】基本操作与基础命令

【探花交友】MongoDB基础

又是三年

【C】指针、指针变量、解引用

Dolby Vision 杜比视界插件

【算法基础】广度优先搜索算法

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【算法基础】广度优先搜索算法

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款