2023年6月22日发(作者：)

图⽂详解两种算法：深度优先遍历（DFS）和⼴度优先遍历（BFS）参考⽹址：深度优先遍历(Depth First Search, 简称 DFS) 与⼴度优先遍历(Breath First Search)是图论中两种⾮常重要的算法，⽣产上⼴泛⽤于拓扑排序，寻路(⾛迷宫)，搜索引擎，爬⾍等，也频繁出现在 leetcode，⾼频⾯试题中。本⽂将会从以下⼏个⽅⾯来讲述深度优先遍历，⼴度优先遍历，相信⼤家看了肯定会有收获。深度优先遍历，⼴度优先遍历简介习题演练DFS，BFS 在搜索引擎中的应⽤深度优先遍历，⼴度优先遍历简介深度优先遍历主要思路是从图中⼀个未访问的顶点 V 开始，沿着⼀条路⼀直⾛到底，然后从这条路尽头的节点回退到上⼀个节点，再从另⼀条路开始⾛到底...，不断递归重复此过程，直到所有的顶点都遍历完成，它的特点是不撞南墙不回头，先⾛完⼀条路，再换⼀条路继续⾛。树是图的⼀种特例(连通⽆环的图就是树)，接下来我们来看看树⽤深度优先遍历该怎么遍历。1、我们从根节点 1 开始遍历，它相邻的节点有 2，3，4，先遍历节点 2，再遍历 2 的⼦节点 5，然后再遍历 5 的⼦节点 9。2、上图中⼀条路已经⾛到底了(9是叶⼦节点，再⽆可遍历的节点)，此时就从 9 回退到上⼀个节点 5，看下节点 5 是否还有除 9 以外的节点，没有继续回退到 2，2 也没有除 5 以外的节点，回退到 1，1 有除 2 以外的节点 3，所以从节点 3 开始进⾏深度优先遍历，如下：3、同理从 10 开始往上回溯到 6, 6 没有除 10 以外的⼦节点，再往上回溯，发现 3 有除 6 以外的⼦点 7，所以此时会遍历 7。3、从 7 往上回溯到 3， 1，发现 1 还有节点 4 未遍历，所以此时沿着 4， 8 进⾏遍历,这样就遍历完成了。完整的节点的遍历顺序如下(节点上的的蓝⾊数字代表)：相信⼤家看到以上的遍历不难发现这就是树的前序遍历,实际上不管是前序遍历，还是中序遍历，亦或是后序遍历，都属于深度优先遍历。那么深度优先遍历该怎么实现呢，有递归和⾮递归两种表现形式，接下来我们以⼆叉树为例来看下如何分别⽤递归和⾮递归来实现深度优先遍历。1、递归实现递归实现⽐较简单，由于是前序遍历，所以我们依次遍历当前节点，左节点，右节点即可，对于左右节点来说，依次遍历它们的左右节点即可，依此不断递归下去，直到叶节点(递归终⽌条件)，代码如下：1. public class Solution {

2. private 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. = value;

18. = left;

19. = right;

20. }

21. }

22.

23. public static void dfs(Node treeNode) {

24. if (treeNode == null) {

25. return;

26. } 27. // 遍历节点

28. process(treeNode)

29. // 遍历左节点

30. dfs();

31. // 遍历右节点

32. dfs();

33. }

34. }

递归的表达性很好，也很容易理解，不过如果层级过深，很容易导致栈溢出。所以我们重点看下⾮递归实现。2、⾮递归实现仔细观察深度优先遍历的特点，对⼆叉树来说，由于是先序遍历(先遍历当前节点，再遍历左节点，再遍历右节点)，所以我们有如下思路：对于每个节点来说，先遍历当前节点，然后把右节点压栈，再压左节点(这样弹栈的时候会先拿到左节点遍历，符合深度优先遍历要求)。弹栈，拿到栈顶的节点，如果节点不为空，重复步骤 1， 如果为空，结束遍历。我们以以下⼆叉树为例来看下如何⽤栈来实现 DFS。整体动图如下：整体思路还是⽐较清晰的，使⽤栈来将要遍历的节点压栈，然后出栈后检查此节点是否还有未遍历的节点，有的话压栈，没有的话不断回溯(出栈)，有了思路，不难写出如下⽤栈实现的⼆叉树的深度优先遍历代码：1. /**

2. * 使⽤栈来实现 dfs

3. * @param root

4. */

5. public static void dfsWithStack(Node root) {

6. if (root == null) {

7. return;

8. }

9.

10. Stack stack = new Stack<>();

11. // 先把根节点压栈

12. (root);

13. while (!y()) {

14. Node treeNode = ();

15. // 遍历节点

16. process(treeNode)

17.

18. // 先压右节点

19. if ( != null) {

20. ();

21. }

22.

23. // 再压左节点

24. if ( != null) {

25. ();

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. if (root == null) {

7. return;

8. }

9. Queue stack = new LinkedList<>();

10. (root);

11.

12. while (!y()) {

13. Node node = ();

14. n("value = " + );

15. Node left = ;

16. if (left != null) {

17. (left);

18. }

19. Node right = ;

20. if (right != null) {

21. (right);

22. }

23. }

24. }

习题演练接下来我们来看看在 leetcode 中出现的⼀些使⽤ DFS，BFS 来解题的题⽬：1. leetcode 104，111: 给定⼀个⼆叉树，找出其最⼤/最⼩深度。

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

2. /

3. 9 20

4. /

5. 15 7

则它的最⼩深度 2，最⼤深度 3。解题思路：这题⽐较简单，只不过是深度优先遍历的⼀种变形，只要递归求出左右⼦树的最⼤/最⼩深度即可，深度怎么求，每递归调⽤⼀次函数，深度加⼀。不难写出如下代码：1. /**

2. * leetcode 104: 求树的最⼤深度

3. * @param node

4. * @return

5. */

6. public static int getMaxDepth(Node node) {

7. if (node == null) {

8. return 0;

9. }

10. int leftDepth = getMaxDepth() + 1;

11. int rightDepth = getMaxDepth() + 1;

12. return (leftDepth, rightDepth);

13. }

14.

15. /**

16. * leetcode 111: 求树的最⼩深度

17. * @param node

18. * @return

19. */

20. public static int getMinDepth(Node node) {

21. if (node == null) {

22. return 0;

23. }

24. int leftDepth = getMinDepth() + 1;

25. int rightDepth = getMinDepth() + 1;

26. return (leftDepth, rightDepth);

27. } leetcode 102: 给你⼀个⼆叉树，请你返回其按层序遍历得到的节点值。(即逐层地，从左到右访问所有节点)。⽰例，给定⼆叉树：[3,9,20,null,null,15,7]。1. 3

2. /

3. 9 20

4. /

5. 15 7

返回其层次遍历结果：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> bfsWithBinaryTreeLevelOrderTraversal(Node root) {

6. if (root == null) {

7. // 根节点为空，说明⼆叉树不存在，直接返回空数组

8. return ();

9. }

10.

11. // 最终的层序遍历结果

12. List> result = new ArrayList<>();

13.

14. Queue queue = new LinkedList<>();

15. (root);

16.

17. while (!y()) {

18. // 记录每⼀层

19. List level = new ArrayList<>();

20. int levelNum = ();

21. // 遍历当前层的节点

22. for (int i = 0; i < levelNum; i++) {

23. Node node = ();

24. // 队⾸节点的左右⼦节点⼊队,由于 levelNum 是在⼊队前算的，所以⼊队的左右节点并不会在当前层被遍历到

25. if ( != null) {

26. ();

27. }

28. if ( != null) {

29. ();

30. }

31. ();

32. }

33. (level);

34. }

35.

36. return result;

37. }

Python 代码1. class Solution:

2. def levelOrder(self, root):

3. """

4. :type root: TreeNode

5. :rtype: List[List[int]] 6. """

7. res = [] #嵌套列表，保存最终结果

8. if root 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 = t() #弹出队⾸节点

18. #队⾸节点的左右孩⼦⼊队

19. if is not None:

20. ()

21. if is not None:

22. ()

23. () #队⾸节点的值压⼊本层

24. thislevel-=1

25. (lev)

26. return res

这题⽤ BFS 是显⽽易见的，但其实也可以⽤ DFS， 如果在⾯试中能⽤ DFS 来处理，会是⼀个⽐较⼤的亮点。⽤ DFS 怎么处理呢，我们知道， DFS 可以⽤递归来实现，其实只要在递归函数上加上⼀个「层」的变量即可，只要节点属于这⼀层，则把这个节点放⼊相当层的数组⾥，代码如下：1. private static final List> 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. if (root == null) {

9. return;

10. }

11.

12. if (TRAVERSAL_() < level + 1) {

13. TRAVERSAL_(new ArrayList<>());

14. }

15.

16. List levelList = TRAVERSAL_(level);

17. ();

18.

19. // 遍历左结点

20. dfs(, level + 1);

21.

22. // 遍历右结点

23. dfs(, level + 1);

24. }

DFS，BFS 在搜索引擎中的应⽤我们⼏乎每天都在 Google, Baidu 这些搜索引擎，那⼤家知道这些搜索引擎是怎么⼯作的吗，简单来说有三步：1、⽹页抓取搜索引擎通过爬⾍将⽹页爬取，获得页⾯ HTML 代码存⼊数据库中2、预处理索引程序对抓取来的页⾯数据进⾏⽂字提取，中⽂分词，(倒排)索引等处理，以备排名程序使⽤3、排名⽤户输⼊关键词后，排名程序调⽤索引数据库数据，计算相关性，然后按⼀定格式⽣成搜索结果页⾯。我们重点看下第⼀步，⽹页抓取。这⼀步的⼤致操作如下：给爬⾍分配⼀组起始的⽹页，我们知道⽹页⾥其实也包含了很多超链接，爬⾍爬取⼀个⽹页后，解析提取出这个⽹页⾥的所有超链接，再依次爬取出这些超链接，再提取⽹页超链接。。。，如此不断重复就能不断根据超链接提取⽹页。如下图⽰：如上所⽰，最终构成了⼀张图，于是问题就转化为了如何遍历这张图，显然可以⽤深度优先或⼴度优先的⽅式来遍历。如果是⼴度优先遍历，先依次爬取第⼀层的起始⽹页，再依次爬取每个⽹页⾥的超链接，如果是深度优先遍历，先爬取起始⽹页 1，再爬取此⽹页⾥的链接...，爬取完之后，再爬取起始⽹页 2...实际上爬⾍是深度优先与⼴度优先两种策略⼀起⽤的，⽐如在起始⽹页⾥，有些⽹页⽐较重要(权重较⾼)，那就先对这个⽹页做深度优先遍历，遍历完之后再对其他(权重⼀样的)起始⽹页做⼴度优先遍历。总结DFS 和 BFS 是⾮常重要的两种算法，⼤家⼀定要掌握，本⽂为了⽅便讲解，只对树做了 DFS，BFS，⼤家可以试试如果⽤图的话该怎么写代码，原理其实也是⼀样，只不过图和树两者的表⽰形式不同⽽已，DFS ⼀般是解决连通性问题，⽽ BFS ⼀般是解决最短路径问题，之后有机会我们会⼀起来学习下并查集，Dijkstra, Prism 算法等，敬请期待!