算法模板(二)(相关话题:广度优先搜索BFS)
2023-09-11 14:20:01 时间
模板介绍
BFS 的核心思想应该不难理解的,就是把一些问题抽象成图,从一个点开始,向四周开始扩散。一般来说,我们写 BFS 算法都是用「队列」这种数据结构,每次将一个节点周围的所有节点加入队列。
BFS 相对 DFS 的最主要的区别是:BFS 找到的路径一定是最短的,但代价就是空间复杂度比 DFS 大很多
1、为什么 BFS 可以找到最短距离,DFS 不行吗?
首先,你看 BFS 的逻辑,depth
每增加一次,队列中的所有节点都向前迈一步,这保证了第一次到达终点的时候,走的步数是最少的。
DFS 不能找最短路径吗?其实也是可以的,但是时间复杂度相对高很多。
你想啊,DFS 实际上是靠递归的堆栈记录走过的路径,你要找到最短路径,肯定得把二叉树中所有树杈都探索完才能对比出最短的路径有多长对不对?
而 BFS 借助队列做到一次一步「齐头并进」,是可以在不遍历完整棵树的条件下找到最短距离的。
形象点说,DFS 是线,BFS 是面;DFS 是单打独斗,BFS 是集体行动。这个应该比较容易理解吧。
2、既然 BFS 那么好,为啥 DFS 还要存在?
BFS 可以找到最短距离,但是空间复杂度高,而 DFS 的空间复杂度较低。
还是拿刚才我们处理二叉树问题的例子,假设给你的这个二叉树是满二叉树,节点总数为N
,对于 DFS 算法来说,空间复杂度无非就是递归堆栈,最坏情况下顶多就是树
相关文章
- 算法题——深度优先搜索
- destoon对搜索表单是否为空进行判断
- destoon7搜索去掉上一级分类进行seo优化
- destoon聚合搜索页面模板
- Java实现 LeetCode 96 不同的二叉搜索树
- github搜索技巧:快速搜到你想要的!
- SAP CRM产品主数据搜索功能的With individual object搜索参数
- hybris backoffice搜索时遇到could not execute full-text query的解决方案
- Atitit 歌曲年份抓取的nlp ai项目 原理通过百度搜索,抓取第一页数据,正则数字,过滤年份。。 显示格式。。歌曲,年份,年份周围前后40字符,方便核对 通过百科抓取比较准确 红尘情歌
- 【hihocoder 1312】搜索三·启发式搜索(普通广搜做法)
- 98. 验证二叉搜索树-dfs
- Leetcode 74. 搜索二维矩阵
- Python: 字符串搜索和匹配,re.compile() 编译正则表达式字符串,然后使用match() , findall() 或者finditer() 等方法
- 【LeetCode】33. 搜索旋转排序数组