BlockLune's Blog

首页 标签 关于 |

初探深度优先搜索（DFS）和广度优先搜索（BFS）

published at 2022-11-22
algorithmdata-structuregraph-traversalstack-queue

深度优先搜索（DFS，Depth First Search）和广度优先搜索（BFS，Breadth First Search），我从来没弄明白过。是时候努力去好好理解一下了。

B 站找了两个视频看，这篇文章是笔记。

所以图直观还是直接看视频吧…

深度优先搜索

DFS 的搜索过程要结合 栈 来理解，实际上这个过程就是在对一个 栈 在操作。比如我们有这样一张图：

{% mermaid graph TB %} 1((1))===2((2))===4((3))===8((4))===5((5)) 2((2))===5((5)) 1((1))===3((8))===6((6))===8((4)) 3((8))===7((9)) 6((6))===9((7)) {% endmermaid %}

我们建立一个栈，然后开始遍历上边这张图。我们做以下约定：

  • 已经入栈的节点要被标记为已经遍历；
  • 起始节点为 1，将其入栈，作为最初的栈顶；
  • 查看与当前栈顶元素相连并且未被标记的节点，将其入栈；
  • 如果有多个满足 3 中条件的元素，节点序号较小的优先入栈；
  • 当栈顶元素没有相连节点或所有相连节点均已经被标记后，将其出栈。

所以对于上边的图，我们依次进行下面的操作：

  1. 节点 1 入栈，并将其标记；
  2. 查找与当前栈顶元素节点 1 相连并且没有标记的元素，有节点 2 和节点 8，节点 2 优先入栈，将节点 2 标记；
  3. 查找与当前栈顶元素节点 2 相连并且没有标记的元素，有节点 3 和节点 5，节点 3 优先入栈，将节点 3 标记；
  4. 查找与当前栈顶元素节点 3 相连并且没有标记的元素，只有节点 4，节点 4 入栈，并将其标记；
  5. 查找与当前栈顶元素节点 4 相连并且没有标记的元素，有节点 5 和 节点 6 ，节点 5 优先入栈，将节点 5 标记；
  6. 查找与当前栈顶元素节点 5 相连的元素，有节点 2 和节点 4，但均已被标记，所以当前栈顶节点 5 出栈；
  7. 查找与当前栈顶元素节点 4 相连并且没有标记的元素，只有节点 6，节点 6 入栈，并将其标记；
  8. 查找与当前栈顶元素节点 6 相连并且没有标记的元素，有节点 7 和节点 8，节点 7 优先入栈，将节点 7 标记；
  9. 查找与当前栈顶元素节点 7 相连的元素，没有这样的元素，节点 7 出栈；
  10. 查找与当前栈顶元素节点 6 相连并且没有标记的元素，只有节点 8，节点 8 入栈，并将其标记；
  11. 查找与当前栈顶元素节点 8 相连并且没有标记的元素，只有节点 9， 节点 9 入栈，并将其标记；
  12. 查找与当前栈顶元素节点 9 相连并且没有标记的元素，没有这样的元素，节点 9 出栈；
  13. 查看当前栈顶元素节点 8，类似，节点 8 出栈；
  14. 查看当前栈顶元素节点 6，类似，节点 6 出栈；
  15. 查看当前栈顶元素节点 4，类似，节点 4 出栈；
  16. 查看当前栈顶元素节点 3，类似，节点 3 出栈；
  17. 查看当前栈顶元素节点 2，类似，节点 2 出栈；
  18. 查看当前栈顶元素节点 1，类似，节点 1 出栈。

上边对这个栈的操作过程应该如下边所示：

  1. （栈空）

  2. 节点 1

  3. 节点 1、节点 2

  4. 节点 1、节点 2、节点 3

  5. 节点 1、节点 2、节点 3、节点 4

  6. 节点 1、节点 2、节点 3、节点 4、节点 5

  7. 节点 1、节点 2、节点 3、节点 4

  8. 节点 1、节点 2、节点 3、节点 4、节点 6

  9. 节点 1、节点 2、节点 3、节点 4、节点 6、节点 7

  10. 节点 1、节点 2、节点 3、节点 4、节点 6

  11. 节点 1、节点 2、节点 3、节点 4、节点 6、节点 8

  12. 节点 1、节点 2、节点 3、节点 4、节点 6、节点 8、节点 9

  13. 节点 1、节点 2、节点 3、节点 4、节点 6、节点 8

  14. 节点 1、节点 2、节点 3、节点 4、节点 6

  15. 节点 1、节点 2、节点 3、节点 4

  16. 节点 1、节点 2、节点 3

  17. 节点 1、节点 2

  18. 节点 1

  19. （栈空）

宽度优先搜索

BFS 的搜索过程要联系 队列 来理解，约定如下：

  • 已经入队的节点要被标记为已经遍历；
  • 第一个入队的是节点 1，将其作为最初的队首和队尾；
  • 遍历与当前队首相连但未被标记的节点，按照数字大小依次入队，并且移动队尾；
  • 队首移动到下一个元素。

例如对下边这个图：

{% mermaid graph TB %} 1((1))===2((2))===4((4))===8((8)) 2((2))===5((5))===8((8)) 1((1))===3((3))===6((6))===8((8)) 6((6))===9((9)) 3((3))===7((7))===9((9)) {% endmermaid %}

队列维护的情况如下（加粗的表示队首、斜体表示队尾）：

  1. 1、2、3
  2. 1、2、3、4、5
  3. 1、2、3、4、5、6、7
  4. 1、2、3、4、5、6、7、8
  5. 1、2、3、4、5、6、7、8
  6. 1、2、3、4、5、6、7、8、9
  7. 1、2、3、4、5、6、7、8、9
  8. 1、2、3、4、5、6、7、8、9
  9. 1、2、3、4、5、6、7、8、9