熬夜怒肝,图解算法!BFS和DFS的直观解释

这篇具有很好参考价值的文章主要介绍了熬夜怒肝,图解算法!BFS和DFS的直观解释。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、前言

我们首次接触 BFS 和 DFS 时,应该是在数据结构课上讲的 “图的遍历”。还有就是刷题的时候,遍历二叉树我们会经常用到BFS和DFS。它们的实现都很简单,这里我就不哆嗦去贴代码了。

想看代码的可以看《剑指Offer(三十八):二叉树的深度》这个题目就可以利用BFS和DFS进行求解。那么,这两者“遍历” 的序列到底有何差别?

本篇文章就单纯来讲讲它们的区别和各自的应用,不会涉及任何代码。我们以“图的遍历”为例,进行说明。

二、区别

广度优先搜索算法(Breadth-First-Search,缩写为 BFS),是一种利用队列实现的搜索算法。简单来说,其搜索过程和 “湖面丢进一块石头激起层层涟漪” 类似。

深度优先搜索算法(Depth-First-Search,缩写为 DFS),是一种利用递归实现的搜索算法。简单来说,其搜索过程和 “不撞南墙不回头” 类似。

BFS 的重点在于队列,而 DFS 的重点在于递归。这是它们的本质区别。

举个典型例子,如下图,灰色代表墙壁,绿色代表起点,红色代表终点,规定每次只能走一步,且只能往下或右走。求一条绿色到红色的最短路径。

熬夜怒肝,图解算法!BFS和DFS的直观解释

对于上面的问题,BFS 和 DFS 都可以求出结果,它们的区别就是在复杂度上存在差异。我可以先告诉你,该题 BFS 是较佳算法。

BFS示意图:

熬夜怒肝,图解算法!BFS和DFS的直观解释

如上图所示,从起点出发,对于每次出队列的点,都要遍历其四周的点。所以说 BFS 的搜索过程和 “湖面丢进一块石头激起层层涟漪” 很相似,此即 “广度优先搜索算法” 中“广度”的由来。

DFS示意图:

熬夜怒肝,图解算法!BFS和DFS的直观解释

三、总结

现在,你不妨对照着图,再去看看你打印出的遍历序列,是不是一目了然呢?

最后再说下它们的应用方向。

BFS 常用于找单一的最短路线,它的特点是 "搜到就是最优解",而 DFS 用于找所有解的问题,它的空间效率高,而且找到的不一定是最优解,必须记录并完成整个搜索,故一般情况下,深搜需要非常高效的剪枝(剪枝的概念请百度)。

PS:BFS 和 DFS 是很重要的算法,读者如果想要更深入地了解它们,建议去 OJ 或 Leetcode 上找一些相关赛题训练下,一定会给你一个别样的天地。

如上图所示,从起点出发,先把一个方向的点都遍历完才会改变方向...... 所以说,DFS 的搜索过程和 “不撞南墙不回头” 很相似,此即 “深度优先搜索算法” 中“深度”的由来。

最后再送大家一本,帮助我拿到 BAT 等一线大厂 offer 的数据结构刷题笔记,是一位 Google 大神写的,对于算法薄弱或者需要提高的同学都十分受用:

谷歌和阿里大佬的Leetcode刷题笔记

以及我整理的 BAT 算法工程师学习路线,书籍+视频,完整的学习路线和说明,对于想成为算法工程师的,绝对能有所帮助(提取码:jack):

我是如何成为算法工程师的,超详细的学习路线

别光收藏,来个赞哦,笔芯~文章来源地址https://www.toymoban.com/news/detail-423680.html

到了这里,关于熬夜怒肝,图解算法!BFS和DFS的直观解释的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 算法设计与分析实验:DFS与BFS

    目录 一、边界着色 1.1 思路一:DFS 1.2 思路二:BFS 二、课程表II 2.1 思路一:DFS 2.2 思路二:拓扑排序 三、岛屿的最大面积 3.1 具体思路 3.2 思路展示 3.3 代码实现 3.4 复杂度分析 3.5 运行结果 2024-1-31 阴 力扣第1034题 (1)具体思路: 首先,定义一个dfs函数,用于搜索和染色连通

    2024年02月21日
    浏览(34)
  • BFS算法(宽度优先搜索)超强解析 BFS迷宫问题图文详解 DFS与BFS的区别

      前情回顾:DFS练习-迷宫(最短路径)问题详解 一波三折 图片+文字 以及你需要会的基础:手搓数据结构之队列queue C/C++语言版(BFS算法预备知识) 广度优先搜索(Breadth First Search)简称广搜或者 BFS, 是遍历图存储结构的一种算法 。 BFS的原理是 “逐层扩散” ,从起点出发

    2024年02月22日
    浏览(48)
  • 【算法】(BFS/DFS)迷宫路径问题(C语言)

    题目 :现有一迷宫如下图所示,蓝色部分为墙壁,白色部分为通路,入口在左上角(1,1)处,出口在右下角(8,8)处,试找出一条路径以通过该迷宫(路径不能重叠)。 分析 : ① 使用二维数组来存储迷宫,墙用 1 表示,路用 0 表示,如下图所示: 为与题目中的入口坐标

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

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

    2024年01月17日
    浏览(49)
  • 数据结构与算法 | 深搜(DFS)与广搜(BFS)

    在查找二叉树某个节点时,如果把二叉树所有节点理解为解空间,待找到那个节点理解为满足特定条件的解,对此解答可以抽象描述为: 在解空间中搜索满足特定条件的解 ,这其实就是搜索算法(Search)的一种描述。当然也有其他描述,比如是“指一类用于在数据集合中查

    2024年02月08日
    浏览(36)
  • 基础算法之搜素(bfs和dfs模板和例题)

    之前学习了暴力枚举策略,将所有可能的情况都枚举一遍以获得最优解,但是枚举全部元素的效率如同愚公移山,无法应付数据范围稍大的情形。 本节在暴力枚举的基础上介绍搜索算法,包括 深度优先搜索和广度优先搜索 , 从起点开始,逐渐扩大寻找范围,直到找到需要的

    2024年02月16日
    浏览(32)
  • 【算法手札】深入理解宽度遍历(bfs)和深度遍历(dfs)搜索

        算法的重要性不言而喻,现在我们的生活也已经离不开各种算法,一个好的算法能大大提高程序的运行效率,是学习编程的一个重要模块,而遍历算法也是算法里的一个大的模块,今天我们一起来学习一下深度遍历算法(depth first search)和 广度优先遍历(broad first searc

    2024年02月21日
    浏览(45)
  • 红与黑(bfs + dfs 解法)(算法图论基础入门)

    献给阿尔吉侬的花束( 入门级bfs查找 + 模版解读 + 错误示范 在之前的博客当中,详细地介绍了这类题目的解法,今天为大家带来一道类似的题目练练手,后续还会更新更有挑战的题目以及更为详细的解析,喜欢的小伙伴可以点个关注啦! 有一间长方形的房子,地上铺了红色、

    2024年01月20日
    浏览(54)
  • 算法基础学习笔记——⑩DFS与BFS\树与图

    ✨博主:命运之光 ✨专栏:算法基础学习 目录 DFS与BFS树与图 ✨DFS ✨BFS 🍓宽搜流程图如下: 🍓宽搜流程: 🍓广搜模板 ✨树与图 🍓树是特殊的图(连通无环的图) 🍓树与图的存储: 🍓用宽搜框架来搜索图: 前言: 算法学习笔记记录日常分享,需要的看哈O(∩_∩)O,

    2024年02月09日
    浏览(35)
  • 深入探索图算法:用C语言实现BFS和DFS

    图算法是计算机科学中一个重要且有趣的领域,它们在解决许多现实世界的问题时发挥着关键作用。本篇博客将介绍两种常见的图算法:广度优先搜索(BFS)和深度优先搜索(DFS),并提供在C语言中的实现示例。 广度优先搜索是一种用于图遍历的算法,它从起始节点开始逐

    2024年02月12日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包