稀有猿诉

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

BFS and DFS Made Easy

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

基础概念和代码模板

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

广度优先搜索

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

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

广度优先搜索要借助队列来实现,不断的把相邻的节点放入队列,直到队列为空为止,典型的实现如下:

1
2
3
4
5
6
7
8
9
10
# typical BFS
queue = deque()
queue.add(i)
visited[i] = True
while len(queue) > 0:
  u = queue.popleft()
  for v in graph[u]:
      if not visited[v]:
          visited[v] = True
          queue.add(v)

深度优先搜索

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

DFS在树中应用是最多的,特别是二叉树,因为二叉树只有两个方向,一个左子树一个右子树,再借助递归DFS是效率最高的遍历方式。通常DFS用来解决特定路径相关的问题。

另外,递归树也是DFS,因此回溯算法用的就是DFS。

DFS可以借助栈,也可以直接用递归:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# typical DFS with stack
stack = deque()
stack.add(i)
visited[i] = True
while len(stack) > 0:
  u = stack.pop()
  for v in graph[u]:
      if not visited[v]:
          visited[v] = True
          stack.add(v)

# typical DFS with recusion
def dfs(u, visited):
  visited[u] = True
  for v in graph[u]:
      if not visited[v]:
          visited[v] = True
          dfs(v, visited)

在树中的应用

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

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

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

典型题目

题目 题解 说明
662. 二叉树最大宽度 题解
1376. 通知所有员工所需的时间 题解 DFS树最大深度
题解
题解

在图中的应用

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

多源广度优先搜索

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

按层做广度优先搜索

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

典型题目

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

参考资料

Comments