稀有猿诉

十年磨一剑,历炼出锋芒,说话千百句,不如码二行。

BFS and DFS Made Easy

深度优先搜索和广度优先搜索在二维数据结构中有着非常重要和广泛的应用,今天就来好好的学习和总结一下这两种遍历方法。

基础概念和代码模板

先来学习一下基础的概念,其实也并不复杂。

广度优先搜索

BFS(Breadth First Search)是指优先把与当前节点相连的节点遍历,然后再把相连的节点的所有相连节点遍历,直到所有节点都遍历完。看起来就是一层一层的遍历(树),或者一圈一圈的遍历,像水中的波浪一样从中心点不断向外扩散。

它的遍历特点是,能把最近的两个节点优先遍历到,换句话说,它能找到从某个节点开始到另一个节点的最短路径,这一点相当重要,因此在图相关的搜索中用的较多一些。

深度优先搜索

DFS(Depth First Search),顺着节点的一个方向,不断深入,专注于一个方向直到这个方向上没有节点了(到达了叶子,或者到达了边界,或者最后一个节点);然后再回到最初的节点,换一个方向,继续前行,直到所有节点都遍历完成。它的特点是只认准一个方向,不撞南墙不回头。

DFS在树中应用是最多的,因为树只有两个方向,一个左子树一个右子树。通常DFS用来解决特定路径相关的问题。

在树中的应用

树的遍历和路径相关的问题,一般用DFS较为方便,树是最方便用递归的,因此递归 式DFS是解决树的遍历和路径的最广泛的方法。比如,经典的树三种遍历方式(前,中后)如果用递归式DFS来写就相当的简洁。可以参考这篇文章来学习更多关于树的知识。

DFS对于树的大多数问题都是较好的选择,但有一类题,就是层序遍历相关的问题,DFS可能没有优势,因为层序遍历就是用BFS最为直接,通常实践得知,对于树来说,通常BFS的效率要差于DFS。而且对于树来说,BFS能搞定的问题,DFS也一定可以。

那么如何用DFS解决与层有关的问题呢?要借助额外的数据来标记当前节点是在哪一层。树DFS的遍历特点是仍旧是从左下到右下的,而且也是从上到下的(前序而言),因此DFS最先遇到的节点,肯定 是这 一层的第一个节点。DFS也是知道当前节点是属于哪一层的,根节点是第1 层,下一层就是第2层,可以把这个作为参数在DFS过程中传递。额外的数据可以是哈希表,键值就是层序号,值可以节点,当某一层为空时,来的肯定是第一个节点,如果某一层已存在,就可以追加节点,或者依据条件做运算。这样最终也能实现关于层的操作。最为典型的就是题662. 二叉树最大宽度

典型题目

题目 题解 说明
662. 二叉树最大宽度 题解
题解
题解
题解

在图中的应用

对于图来说,因为它可能有多个方向,像矩阵有四个,常规图可能有更多个与其相连的节点,而图的搜索通常是发生在相连的多个节点之间的,因此在图的搜索里面BFS的应用更为广泛。像求一些最短路径,最近距离,拓朴排序等都是用的BFS。

多源广度优先搜索

常规的BFS是单源的,也就是说先把一个顶点入队,然后从这个顶点向与其邻接的顶点扩散(入队)。但有些时候会先把一群符合某种条件的顶点入队,然后从这些顶点开始做BFS,向外扩散,这种称之为多源广度优先搜索。

按层做广度优先搜索

与树中的层序遍历是一样的,在图中也有按层做BFS的时候。比如求岛屿类型的最短路径的时候,就要结合多源BFS,然后再做层序BFS。最为典型的就是题934。

典型题目

题目 题解 说明
200. 岛屿数量 题解 基础
695. 岛屿的最大面积 题解 基础
733. 图像渲染 题解 单源BFS/DFS
542. 01 矩阵 题解 多源BFS
994. 腐烂的橘子 题解 多源BFS
886. 可能的二分法 题解 二分图判定
934. 最短的桥 题解 多源BFS,按层BFS
130. 被围绕的区域 题解 基础
797. 所有可能的路径 题解 DFS,回溯
题解
题解
题解

参考资料

Comments