图文详解两种算法：深度优先遍历（DFS）和广度优先遍历（BFS）

参考网站：图文详解两种算法：深度优先（DFS）和广度优先遍历（BFS） - 51CTO.COM

深度优先遍历(Depth First Search, 简称 DFS) 广度优先遍历(Breath First Search)它是图论中两种非常重要的算法，广泛应用于拓扑排序、道路搜索（迷宫）、搜索引擎、爬虫等，也经常出现 leetcode，在高频面试题中。

本文将从以下几个方面讲述深度优先遍历和广度优先遍历。相信大家看了肯定会有收获。

• 深度优先遍历，广度优先遍历简介
• 习题演练
• DFS，BFS 应用于搜索引擎

深度优先遍历，广度优先遍历简介

深度优先遍历

主要思路是从图中未访问的顶点 V 一开始，沿着一条路走到底，然后从这条路尽头的节点回到上一个节点，然后从另一条路走到底..，重复这个过程，直到所有的顶点都完成，它的特点是不撞南墙不回头，先走一条路，再换一条路继续走。

树是一个特例(连接无环的图是树)。接下来我们来看看树用深度优先遍历怎么遍历。

1、我们从根节点开始 1 开始遍历，相邻节点有 二、三、四、先遍历节点 2，再遍历 2 的子节点 五、再次历历 5 的子节点 9。

2、上图中的一条路已经走到了尽头(9是叶节点，再也没有遍历过的节点)，此时从 9 返回到上一个节点 5，看下节点 5 是否还有除 9 其他节点没有继续返回 2，2 也没有除 5 以外的节点，返回 1，1 有除 2 以外的节点 因此，从节点开始 3 开始深度优先遍历，如下：

3、同理从 10 开始向上追溯 6, 6 没有除 10 以外的子节点，然后向上追溯，发现 3 有除 6 以外的子点 7.所以这个时候会遍历 7。

3、从 7 往上回溯到 3， 1，发现 1 还有节点 4 没有遍历，所以这个时候沿着 4， 8 通过这种方式完成了遍历。

完整节点的遍历顺序如下(蓝色数字代表节点)：

相信大家看到上面的遍历，不难发现这是树的前序遍历。其实无论是前序遍历、中序遍历还是后序遍历，都属于深度优先遍历。

那么如何实现深度优先遍历呢？有两种表现形式：递归和非递归。接下来，让我们以二叉树为例，看看如何分别使用递归和非递归来实现深度优先遍历。

1、递归实现

递归的实现相对简单。因为是前序遍历，我们可以依次遍历当前节点、左节点和右节点。对于左右节点，我们可以依次遍历它们的左右节点，并继续递归到叶节点（递归终止条件）。代码如下：

1. public class Solution { 2. static class Node { 3.         /** 4.          * 节点值 5.          */ 6. public int value; 7.         /** 8.          * 左节点 9.          */ 10. public Node left; 11.         /** 12.          * 右节点 13.          */ 14. public Node right; 15.  16. public Node(int value, Node left, Node right) { 17.             this.value = value; 18. left = left; 19. right = right; 20.         } 21.     } 22.  23. public static void dfs(Node treeNode) { 24. null) { 25. return; 26.         } 27.         // 遍历节点 28.         process(treeNode) 29.         // 遍历左节点 30. left); 31.         // 遍历右节点 32. right); 33.     } 34. }

递归的表达性很好，很容易理解，但如果层次太深，很容易导致栈溢出。因此，我们将重点关注非递归的实现。

2、非递归实现

仔细观察深度优先遍历的特点。对于二叉树，我们有以下想法：

对于每个节点，先通过当前节点，然后按下右节点，然后按下左节点（以便在弹奏堆栈时获得左节点通过，以满足深度优先通过的要求）。

弹栈，拿到栈顶的节点，如果节点不是空的，重复步骤 1， 若为空，则结束遍历。

以下二叉树为例，看看如何用栈来实现 DFS。

整体动图如下：

整体思路还是比较清晰的。使用堆栈将覆盖的节点堆栈，然后检查节点是否有未覆盖的节点。如果有的话堆栈，如果没有，就不断追溯(堆栈)。有了思路，就不难写出以下用堆栈实现的二叉树深度优先覆盖代码:

1. /** 2.  * 用栈来实现 dfs 3.  * @param root 4.  */ 5. public static void dfsWithStack(Node root) { 6. null) { 7. return; 8.     } 9.  10.     Stack<Node> stack = new Stack<>(); 11.     // 先把根节点压栈 12.     stack.push(root); 13.     while (!stack.isEmpty()) { 14.         Node treeNode = stack.pop(); 15.         // 遍历节点 16.         process(treeNode) 17.  18.         // 先压右节点 19. right != null) { 20. right); 21.         } 22.  23.         // 再压左节点 24. left != null) { 25. left); 26.         } 27.     } 28. }

可以看出，代码并不复杂，也不用担心递归层次太深造成的栈溢出问题。

广度优先遍历

广度优先遍历，是指从图中未遍历的节点出发，先遍历这个节点的相邻节点，再依次遍历每个相邻节点的相邻节点。

上述树木的广度优先遍历图如下，每个节点的值都是它们的遍历顺序。因此，广度优先遍历也称为层序遍历和第一层（节点） 1)重复第二层(节点) 2、3、4)、第三层(5、6、7、8)、第四层(9、10)。

栈用于深度优先遍历，队列用于实现广度优先遍历。让我们以下二叉树为例，看看如何利用队列实现广度优先遍历。

动图如下：

相信看完以上动图，写下以下代码并不难:

1. /** 2.  * 实现使用队列 bfs 3.  * @param root 4.  */ 5. private static void bfs(Node root) { 6. null) { 7. return; 8.     } 9.     Queue<Node> stack = new LinkedList<>(); 10. add(root); 11.  12.     while (!stack.isEmpty()) { 13.         Node node = stack.poll(); 14. out.println("value = " + node.value); 15. left = node.left; 16. left != null) { 17. add(left); 18.         } 19. right = node.right; 20. right != null) { 17. add(left); 18.         } 19. right = node.right; 20. right != null) { 21. add(right); 22.         } 23.     } 24. }

习题演练

接下来我们来看看 leetcode 有些用途出现在中间 DFS，BFS 来解题的题目：

1. leetcode104，111:给定一棵二叉树，找出它的最大/最小深度。

例如：给定二叉树 [3,9,20,null,null,15,7],

1. 3
2. /\
3. 920
4. /\
5. 157

它的最小深度 2，最大深度 3。

解决问题的想法：这个问题相对简单。这只是一种深度优先的变形。只要递归找到左右子树的最大/最小深度，如何找到深度，每递归调用一个函数，并添加一个深度。不难编写以下代码：

1. /** 2.  * leetcode 104: 求树的最大深度 3.  * @param node 4. return 5.  */ 6. public static int getMaxDepth(Node node) { 7. null) { 8. return 0; 9.     } 10. int leftDepth = getMaxDepth(node.left) + 1; 11. int rightDepth = getMaxDepth(node.right) + 1; 12. return Math.max(leftDepth, rightDepth); 13. } 14.  15. /** 16.  * leetcode 111: 求树的最小深度 17.  * @param node 18. return 19.  */ 20. public static int getMinDepth(Node node) { 21. null) { 22. return 0; 23.     } 24. int leftDepth = getMinDepth(node.left) + 1; 25. int rightDepth = getMinDepth(node.right) + 1; 26. return Math.min(leftDepth, rightDepth); 27. }

leetcode 102: 给你一棵二叉树，请按顺序返回节点值。(即从左到右逐层访问所有节点)。例如，给定二叉树:[3，9，20，null,null,15,7]。

1. 3
2. /\
3. 920
4. /\
5. 157

返回其层次的遍历结果：

1. [
2. [3],
3. [9,20],
4. [15,7]
5. ]

解决问题的想法：显然，这个问题是广度优先遍历的变体。在广度优先遍历的过程中，只需将每层节点添加到同一数组中即可。问题的关键在于，在遍历同一层节点之前，必须事先计算同一层节点的数量（即队列中现有元素的数量），因为 BFS 它是由队列实现的，左右子节点将在整个过程中不断进入队列。记住这一点！动图如下：

根据上述动图思路，不难得出代码如下：

Java 代码1. /** 2.  * leetcdoe 102: 二叉树层序遍历， 使用 bfs 3.  * @param root 4.  */ 5. private static List<List<Integer>> bfsWithBinaryTreeLevelOrderTraversal(Node root) { 6. null) { 7.         // 根节点为空，说明二叉树不存在，直接返回空数组 8. return Arrays.asList(); 9.     } 10.  11.     // 最终层序遍历结果 12. Integer>> result = new ArrayList<>(); 13.  14.     Queue<Node> queue = new LinkedList<>(); 15.     queue.offer(root); 16.  17.     while (!queue.isEmpty()) { 18.         // 记录每一层 19. Integer> level = new ArrayList<>(); 20. int levelNum = queue.size(); 21.         // 遍历当前层的节点 22. for (int i = 0; i < levelNum; i++) { 23.             Node node = queue.poll(); 24.             // 队首节点左右子节点入队，由于 levelNum 是在入队前计算的，所以入队的左右节点不会在当前层被覆盖 25. left != null) { 26. add(node.left); 27.             } 28. right != null) { 29. add(node.right); 30.             } 31. level.add(node.value); 32.         } 33. add(level); 34.     } 35.  36. return result; 37. }

Python 代码1. class Solution: 2.     def levelOrder(self, root): 3. """ 4.         :type root: TreeNode 5. int]] 6. """ 7.         res = []  #嵌套列表，保存最终结果 8. is None: 9. return res 10.          11. from collections import deque 12.         que = deque([root])  #队列，保存待处理的节点 13.         while len(que)!=0: 14.             lev = []  #保存该层节点值的列表 15.             thislevel = len(que)  #该层节点的数量 16.             while thislevel!=0: 17.                 head = que.popleft()  #弹出队的第一节点 18.                 #队伍第一节点左右孩子入队 19. left is not None: 20. left) 21. right is not None: 22. right) 23.                 lev.append(head.val)  #队第一节点的值压入本层 24.                 thislevel-=1 25.             res.append(lev) 26. return res

这题用 BFS 很明显，但也可以使用 DFS， 如果可以在面试中使用 DFS 处理它将是一个相对较大的亮点。

用 DFS 我们知道怎么处理， DFS 它可以通过递归来实现。事实上，只要在递归函数上添加一个函数「层」只要节点属于这一层，将节点放入相同层的数组中，代码如下：

1. private static final List<List<Integer>> TRAVERSAL_LIST  = new ArrayList<>(); 2. /** 3.  * leetcdoe 102: 二叉树层序遍历， 使用 dfs 4.  * @param root 5. return 6.  */ 7. private static void dfs(Node root, int level) { 8. null) { 9. return; 10.     } 11.  12. size() < level + 1) { 13. add(new ArrayList<>()); 14.     } 15.  16. Integer> levelList = TRAVERSAL_LIST.get(level); 17. add(root.value); 18.  19.     // 遍历左结点 20. left, level + 1); 21.  22.     // 遍历右结点 23. right, level + 1); 24. }

DFS，BFS 我们几乎每天都在搜索引擎中使用它 Google, Baidu 你知道这些搜索引擎是如何工作的吗？简单地说，有三个步骤：

1、网页抓取

搜索引擎通过爬虫爬网页获取页面 HTML 在数据库中存储代码

2、预处理

索引程序用于提取捕获的页面数据、中文分词、(倒排)索引等。

3、排名

用户输入关键字后，排名程序调用索引数据库数据，计算相关性，然后以一定的格式生成搜索结果页面。

让我们关注第一步，抓取网页。

这一步的一般操作如下：为爬虫分配一组初始网页，我们知道网页实际上包含了很多超链接，爬虫爬一个网页，分析和提取网页中的所有超链接，然后依次爬出这些超链接，然后提取网页超链接。这样，您就可以根据超链接不断地提取网页。如下图所示：

如上所示，它最终构成了一张图片，因此问题转化为如何遍历这张图片。显然，它可以通过深度优先或广度优先来遍历。

如果是广度优先遍历，先爬第一层的起始网页，再爬每个网页的超链接。如果是深度优先遍历，先爬起始网页。 1.爬取此网页中的链接..，爬行后，爬行起始网页 2...

事实上，爬虫是两种策略：深度优先和广度优先。例如，在起始网页中，一些网页更重要（权重较高），然后先对网页进行深度优先遍历，然后对其他（权重相同）起始网页进行广度优先遍历。

总结

DFS 和 BFS 这是两种非常重要的算法。我们必须掌握它们。为了方便解释，本文只对树做了解释 DFS，BFS，你可以试着用图片写代码，原理其实是一样的，只是图片和树的表达形式不同，DFS 一般是解决连通性问题， BFS 一般是解决最短路径问题，然后我们有机会一起学习和收集，Dijkstra, Prism 算法等，请期待！