算法模版:暴力搜索之BFS

简介: 算法模版:暴力搜索之BFS

前言


唤我沈七就好。


往期专栏:

暴力搜索之DFS

因为BFS需要靠队列来实现,所以在阅读下面的文章时,需要用先了解一下什么是队列。

可以看我之前对队列的讲解。

模拟数据结构之队列


基本概念


BFS:是 Breadth-First-Search 简称,即广度优先搜索算法。

DFS 一样也是一种用于遍历或搜索树或图的算法。不同的是,BFS是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。而 DFS 是沿着树的深度遍历树的节点。


BFS 也被称为层序遍历,即一层一层的遍历,这样效率就高的多,所以相对于 DFS 指数级枚举,BFS 明显是更快的。

因为要同时遍历每一层的结点,所以我们要借助队列保存未被检测的结点。结点按照宽度优先的次序被访问和进出队列。而从队列中取出的顺序即为层序遍历的顺序。


算法思想


BFS 遍历有一个很重要的特点就是,第一个到达目标节点一定是最短路径。

如下图,因为BFS是一层一层的遍历且每一层距离根节点的距离都相同,遍历顺序由内而外,故BFS每到达一个目标节点一定是最短路径。

所以根据这一个特性 BFS 可以解决最短问题。


12.gif


必备概念


1. STL queue


我一般写BFS喜欢用 STL 的现成实现好的队列 queue。

当然你也可以用数组模拟实现队列。如果想了解如果用数组模拟队列,可以看我这篇文章。

模拟数据结构之队列

接下来我简单的介绍一下 STL queue 的使用方法。


queue<pair<int,int>> q;
q.front()  返回队头元素
q.push()   将元素入队
q.pop()    弹出队头元素


这里我定义的队列类型是 pair ,这是一个二元组,其实简单说这就是一个只有两个变量的结构体。

只不过直接用 pair 来定义方便一些。

定义成二元组,是为了方便表示坐标 ( x , y )。

初次以外还有一些常用的小优化


#define x first
#define y second 
typedef pair<int,int>PII;
queue<PII> q;


这样做的目的完全是为了简化代码。

typedef可以重新定义 数据结构 的名称,改成 PII 的单纯是为了简化代码。

fist和second是pair二元组第一和第二个元素,分别通过宏定义用 x 和 y 代替 也是为了简化代码


2 . 偏移量数组


int pos[4][2]={-1,0,0,1,1,0,0,-1};  扩展方法:偏移量数组


这是一个扩展某一个坐标周围的点的绝佳利器。

详细介绍我在我第一篇博客里有详细介绍,有兴趣的同学可以看看。

C/C++实现蛇形矩阵(超详解)


常用模板


伪代码模板


void BFS ()
{
  ① 初始化队列
  ② 将起点入队
  ③ 标记起点已经被访问
  ④ while( 队列不空时 )
  {
   ⑤ 取出队首元素 u ,存放到 t 变量里 ,u 元素出队
   ⑥ 扩展 t 结点
   {
    ⑦ 判重新节点
    ⑧ 如果未被访问,且满足要求,记录当前点到起点的距离
    ⑨ 标记扩展的新结点
    ⑩ 将扩展的新节点入队
   }
   }
}


C++ 模板


#define x first
#define y second 
typedef pair<int,int>PII;
queue<PII> q; STL 的队列,适用的是一个二元组,方便表示坐标。
q.push(start) ;          初始状态入队 
while(!q.empty())      当队列不空的时候。
PII t=q.front();
q.pop();                 取出队头元素,放到 t 里面去
 int pos[4][2]={-1,0,0,1,1,0,0,-1}; 扩展方法:偏移量数组
for(int i=0;i<4;i++)    扩展t结点
{
  int tx=t.x+pos[i][0];
  int ty=t.y+pos[i][1];
    if(g[tx][ty]=='#')continue;  判重新节点
    if(g[tx][ty]=='.') 
    {
        dis[tx][ty]=dis[t.x][t.y]+1;  记录当前点到起点的距离;
        g[tx][ty]='#';   标记好已经走过路
        q.push({tx,ty}); 确定是新节点后入队
    }                    
}


或许读者到现在也是懵懵懂懂,笔者能力有限,没办法把为什么这样做讲解的通俗易懂,如果实在想搞明白原理的话,可以去 AcWing 算法基础课中一探究竟。

而在我看来,只要牢记模板,做出题来也不是问题。

下面我就讲解一下能用BFS解决的经典的走迷宫的问题


经典例题:走迷宫


给定一个 n×m 的二维整数数组,用来表示一个迷宫,数组中只包含 0 或 1,其中 0 表示可以走的路,1 表示不可通过的墙壁。

有一个人位于左上角 ( 1 , 1 )处,已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问,该人从左上角移动至右下角 ( n , m ) 处,至少需要移动多少次。


分析:提炼题目大意,此题就是求解从迷宫的左上角到迷宫的右下角,在不碰到障碍的最短路径是多少。因为是最短路径问题, 故用 BFS 解决相对容易。


详细的解释都在代码里~


#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second 
int n,m;
typedef pair<int,int>PII;
int a[110][110];   储存地图
int dis[110][110];  储存距离
int pos[4][2]={-1,0,0,1,1,0,0,-1}; 偏移量数组
void bfs(PII start)
{
    queue<PII>q;  
    q.push(start);  初始状态入队
    while(!q.empty())  队列不空时
    {
        PII t=q.front();        取出队首元素,存放到 t 变量里 ,元素出队
        q.pop();      元素出队
        for (int i = 0; i < 4; i ++ ) 扩展 t 结点
    {
       int tx=t.x+pos[i][0],ty=t.y+pos[i][1];
       if(a[tx][ty]==-1||a[tx][ty]==1)continue; 判断是否越界或者碰到障碍
       if(a[tx][ty]==0)  如果未被访问,
       {
           dis[tx][ty]=dis[t.x][t.y]+1; 记录当前点到起点的距离
           a[tx][ty]=-1;       标记扩展的新结点被访问
           q.push({tx,ty});    将扩展的新节点入队
       }
       if(tx==n&&ty==m) 如果到达右下角
       {
       cout<<dis[tx][ty]; 返回右下角到起点的距离
       return;
       }
    }
    }
}
int main()
{
    cin>>n>>m;
    memset(a, -1, sizeof a); 初始化为 -1 ,这样方便 判断边界
    for (int i = 1; i <= n; i ++ ) 从1开始读入地图方便判断边界,这样地图都会被初始化的 -1 包围
    for (int j = 1; j <= m; j ++ ) 这样判断扩展的点是否越界时,只要判断是不是 -1 即可
    {
        cin>>a[i][j];
    }
    PII start; 定义一个二元组,储存起点,传入到BFS函数里
    start.x=1,start.y=1;
    bfs(start);
    return 0;
}

完结散花


ok以上就是对 暴力搜索之BFS 的全部讲解啦,很感谢你能看到这儿啦。如果有遗漏、错误或者有更加通俗易懂的讲解,欢迎小伙伴私信我,我后期再补充完善。


题目练习


检验知识是否学会当然是不断刷题啦,下面我给出一部分DFS相关的一些经典题目。

后续如果我有时间就更新这部分知识的题解,到时候就可以配套学习啦。


献给阿尔吉侬的花束

八数码


参考文章


参考文献

https://www.acwing.com/activity/content/19/


相关文章
|
3月前
|
算法
【算法】二分算法——搜索插入位置
【算法】二分算法——搜索插入位置
|
4天前
|
算法 搜索推荐 数据库
二分搜索:高效的查找算法
【10月更文挑战第29天】通过对二分搜索的深入研究和应用,我们可以不断挖掘其潜力,为各种复杂问题提供高效的解决方案。相信在未来的科技发展中,二分搜索将继续发挥着重要的作用,为我们的生活和工作带来更多的便利和创新。
10 1
|
1月前
|
算法 决策智能
基于禁忌搜索算法的VRP问题求解matlab仿真,带GUI界面,可设置参数
该程序基于禁忌搜索算法求解车辆路径问题(VRP),使用MATLAB2022a版本实现,并带有GUI界面。用户可通过界面设置参数并查看结果。禁忌搜索算法通过迭代改进当前解,并利用记忆机制避免陷入局部最优。程序包含初始化、定义邻域结构、设置禁忌列表等步骤,最终输出最优路径和相关数据图表。
|
2月前
|
大数据 UED 开发者
实战演练:利用Python的Trie树优化搜索算法,性能飙升不是梦!
在数据密集型应用中,高效搜索算法至关重要。Trie树(前缀树/字典树)通过优化字符串处理和搜索效率成为理想选择。本文通过Python实战演示Trie树构建与应用,显著提升搜索性能。Trie树利用公共前缀减少查询时间,支持快速插入、删除和搜索。以下为简单示例代码,展示如何构建及使用Trie树进行搜索与前缀匹配,适用于自动补全、拼写检查等场景,助力提升应用性能与用户体验。
50 2
|
1月前
|
机器学习/深度学习 存储 算法
数据结构与算法——BFS(广度优先搜索)
数据结构与算法——BFS(广度优先搜索)
|
1月前
|
存储 算法 C++
【搜索算法】 跳马问题(C/C++)
【搜索算法】 跳马问题(C/C++)
|
1月前
|
人工智能 算法 Java
【搜索算法】数字游戏(C/C++)
【搜索算法】数字游戏(C/C++)
|
3月前
|
存储 算法
BFS算法的实现
BFS算法的实现
46 1
|
3月前
|
机器学习/深度学习 算法 文件存储
【博士每天一篇文献-算法】 PNN网络启发的神经网络结构搜索算法Progressive neural architecture search
本文提出了一种名为渐进式神经架构搜索(Progressive Neural Architecture Search, PNAS)的方法,它使用顺序模型优化策略和替代模型来逐步搜索并优化卷积神经网络结构,从而提高了搜索效率并减少了训练成本。
53 9
|
3月前
|
算法
【算法】递归、搜索与回溯——汉诺塔
【算法】递归、搜索与回溯——汉诺塔