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

基础概念和代码模板

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

广度优先搜索

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. 二叉树最大宽度。

典型题目

在图中的应用

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

多源广度优先搜索

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

按层做广度优先搜索

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

典型题目

参考资料

• BFS——广度优先算法（Breadth First Search）
• DFS——深度优先算法（Depth First Search）
• BFS Vs. DFS: Know the Difference with Example
• Breadth-First Search (BFS)
• Depth-First Search (DFS)
• Depth First Search or DFS for a Graph