广度优先搜索(BFS)

这篇具有很好参考价值的文章主要介绍了广度优先搜索(BFS)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

注意:本内容主要是介绍用BFS实现图的遍历,所以需要对图的结构有所了解。

一、什么是BFS?

BFS(Breadth First Search,广度优先搜索,又名宽度优先搜索),与深度优先算法DFS往一个方向“死磕到底,不撞南墙不回头”的思维方式不同,广度优先搜索算法关注的重点在于对每一层结点进行下一层的访问

二、BFS算法介绍

BFS算法和核心思路就是:从某个点一直把其邻接点走完,然后任选一个邻接点把与之邻接的未被遍历的点走完,如此反复走完所有结点。类似于树的层序遍历。

所以,BFS的核心就是要把当前在哪作为一个状态存储,并将这个状态交给队列进行入队操作

算法步骤(用队列实现)

a) 访问指定起始点。

b) 访问当前顶点的邻接顶点有未被访问的顶点,并将之放入队列中。

c) 删除队列的队首节点。访问当前队列的队首,前面的步骤。直到队列为空。

d) 若途中还有顶点未被访问,则再选一个点作为起始顶点。重复前面的步骤(针对非连通图)。

三.、案例图示

我们直接上案例进行说明,就本图而言,其访问顺序可以是:1--2--3--4--5(并不唯一)

广度优先搜索(BFS)

遍历图的具体步骤如下:

        首先从1开始,1结点处连接着2,3两个结点,所以我们先访问2,3两个结点。同时我们把两个结点按照访问顺序入队,比如,选择2,3为入队顺序,所以之后我们先出队状态2,再来依次访问结点2所连接的4,5两个结点,同样的,按照顺序入队4,5结点,然后操作完状态2之后,我们再出队状态3,并依次访问它的后续,但此时发现3的后续结点已经访问过了,并且检查发现所有的结点都已经被访问完毕,说明遍历结束了。最后我们得到图的遍历次序:1--2--3--4--5

四、相关代码

具体实现遍历图的代码示例:

void BFSL(int pos,pGraph G,int visited[30])//从pos点开始进行广度优先遍历无向图
{
    int queue[G->Vnum];//队列辅助BFS遍历
    int head=0,tail=0;//队头、队尾指针
    Arcnode* p;
    queue[tail]=pos;
    visited[pos]=1;//标记遍历过
    tail++;
    while(head!=tail)
    {
        pos=queue[head];//出队操作
        head++;
        printf("%d ",pos);
        p=G->vertice[pos].firstarc;
        while(p!=NULL)
        {
            if(visited[p->adjvex]==0)//判断是否遍历过
            {
                queue[tail]=p->adjvex;//入队操作
                visited[p->adjvex]=1;//标记遍历过
                tail++;
            }
            p=p->next;
        }
    }
}

 我们使用BFS解决问题的一般模板如下:


/**
 * 返回合适的检索数据
 */
int BFS(Node root, Node target) 
{
    Queue<Node> queue;  //创建队列
    int step = 0;       // 当前队列的步骤点
    // initialize
    add root to queue;
    // BFS
    while (queue is not empty) 
    {
        step = step + 1;
        //步数逐渐增加
        int size = queue.size();
        for (int i = 0; i < size; ++i) 
        {
            Node cur = the first node in queue;
            if cur is target
                return step - 1;
            for (Node next : the neighbors of cur) 
            {//这里常用一个二维方向数组实现
                add next to queue;
            }
            remove the first node from queue;
        }
    }
    return -1;          //出错返回值
}

五、BFS的一些应用场景

BFS算法的实际应用场景:

最典型的有地图搜索,迷宫寻路等这些需要有“状态”以及状态改变场景的搜索算法,同时BFS由于不需要像DFS算法那样回溯,所以效率可能会比DFS更高一些。文章来源地址https://www.toymoban.com/news/detail-405537.html

到了这里,关于广度优先搜索(BFS)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 295.【华为OD机试】智能驾驶( 广度优先搜索(BFS)Java&Python&C++&JS实现)

    🚀点击这里可直接跳转到本专栏,可查阅顶置最新的华为OD机试宝典~ 本专栏所有题目均包含优质解题思路,高质量解题代码(JavaPythonC++JS分别实现),详细代码讲解,助你深入学习,深度掌握!

    2024年03月11日
    浏览(51)
  • 深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)

    目录 深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜) 深度优先搜索(简称“深搜”或DFS) 广度优先搜索 总结 深度优先生成树和广度优先生成树 非连通图的生成森林 深度优先生成森林 广度优先生成森林 图 1 无向图 深度优先搜索的过程类似于树 的先序遍历 ,首先

    2024年01月20日
    浏览(48)
  • 261.【华为OD机试真题】跳马(广度优先搜索(BFS)-Java&Python&C++&JS实现)

    🚀点击这里可直接跳转到本专栏,可查阅顶置最新的华为OD机试宝典~ 本专栏所有题目均包含优质解题思路,高质量解题代码(JavaPythonC++JS分别实现),详细代码讲解,助你深入学习,深度掌握!

    2024年02月20日
    浏览(33)
  • 深度优先搜索(DFS)和广度优先搜索(BFS),用代码讲原理

    以图文的形式对深度搜索和广度搜索的理论进行讲解时,可能会对一些概念有些模糊,且不太清楚怎么把该理论用程序的方式进行复现并解决这一搜索问题(这说的就是本人) 。所以后面我看完了一份实现这两种搜索方法的代码,在这做一个笔记,希望对大家有所帮助。 两

    2024年04月12日
    浏览(50)
  • 深度优先搜索(DFS)和广度优先搜索(BFS)两种算法c++

    深度优先搜索(DFS)和广度优先搜索(BFS)是一种用于遍历或搜索树图的一种算法,在这个过程中保证图或数的每个结点被访问且仅被访问一次,再按照每个结点访问的顺序不同分为深搜和广搜。 本文只讨论这两种算法在搜索方面的应用! 深度优先搜索 ( Depth-First-Search,DFS )它 沿

    2024年02月13日
    浏览(47)
  • Python 算法基础篇:深度优先搜索( DFS )和广度优先搜索( BFS )

    深度优先搜索( DFS )和广度优先搜索( BFS )是两种常用的图遍历算法,用于在图中搜索目标节点或遍历图的所有节点。本篇博客将介绍 DFS 和 BFS 算法的基本概念,并通过实例代码演示它们的应用。 😃😄 ❤️ ❤️ ❤️ 深度优先搜索( DFS )是一种用于遍历或搜索图或树

    2024年02月07日
    浏览(65)
  • C++:第十三讲BFS广度优先搜索

    今天带领大家学一下BFS。 DFS可以看——C++:第十二讲DFS深搜(二)_c++匿名函数dfs-CSDN博客 广度优先搜索(breadth-first search,缩写为bfs)又名宽度优先搜索,是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。其别名又叫BFS,属于一种盲目搜寻法,目的是

    2024年01月25日
    浏览(49)
  • 1432 - 走出迷宫的最少步数-广度优先搜索BFS

    代码

    2024年01月20日
    浏览(78)
  • 图的遍历——深度优先搜索(DFS)与广度优先搜索(BFS)(附带C语言源码)

    个人主页:【😊个人主页】 系列专栏:【❤️数据结构与算法】 学习名言:天子重英豪,文章教儿曹。万般皆下品,惟有读书高——《神童诗劝学》 第一章 ❤️ 学前知识 第二章 ❤️ 单向链表 第三章 ❤️ 递归 … 在此之前我们学习过了图的一些基本概念,如同在二叉树

    2024年02月06日
    浏览(65)
  • 图的遍历(搜索)算法(深度优先算法DFS和广度优先算法BFS)

    从图的某个顶点出发访问遍图中所有顶点,且每个顶点仅被访问一次。(连通图与非连通图) 1、访问指定的起始顶点; 2、若当前访问的顶点的邻接顶点有未被访问的,则任选一个访问之;反之,退回到最近访问过的顶点;直到与起始顶点相通的全部顶点都访问完毕; 3、若

    2024年01月17日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包