Featured image of post DFS(深度优先算法)和BFS(广度优先算法)

DFS(深度优先算法)和BFS(广度优先算法)

遍历寻路算法的开始

BFS全称:Breadth-First-Search
DFS全称:Depth-first search


LeetCode有一题岛屿的数量题目

给定一个由 1(陆地)和 0(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
输入:
11000
11000
00100
00011
输出: 3


这题虽然放在BFS之中,但是使用DFS写起来更容易看懂.

先说这两种算法搜索的区别.

假设有一个输入岛屿参数是这样:

1 1 0 0 0
1 1 1 1 0
1 0 1 0 0
1 0 0 0 0
  • 这一题的答案不管用DFS还是BFS都是1
  1. DFS搜索的顺序总是先往同一个方向发展,直到尽头.
  2. 然后尽头节点发展其他方向,直至所有方向.
  3. 然后回溯到上一个可以发展的节点
  4. DFS像栈,先进后出(回溯)
  • 假设顺序是 ↑↓←→(上下左右)
  • 那么这个岛屿遍历的顺序是:
1 6 0 0 0
2 5 7 9 0
3 0 8 0 0
4 0 0 0 0
  • 1开始,上方向是边界,所以向下搜索一直到4,4到了尽头,而且其他方向没有岛屿,然后回溯到2,2的上下已经搜索过,所以往右边搜索得到5,5向上搜索得到6然后回溯到5,再向右搜索得到7,7的左边已经搜索过,所以向下搜索得到8,然后8附近没有岛屿,回溯搜索到9,至此结束.

  1. BFS搜索的顺序总是先往附近节点发展
  2. 当发展完附近的之后,然后再按附近的顺序再发展附近的节点
  3. BFS 像队列,先进先出,所以我们用队列来解决
  • 假设顺序是 ↑↓←→(上下左右)
  • 那么这个岛屿遍历的顺序是:
1 3 0 0 0
2 5 7 9 0
4 0 8 0 0
6 0 0 0 1
  • (每次搜索接受后丢掉当前节点)从1开始,队列否则有[1],按顺序搜索得到2,3,队列变为[2,3](去掉队列头,后同),然后搜索2的附近得到4,5,队列变为[3,4,5].然后搜索3的附近无节点(5搜索过,重复不处理),队列剩下[4,5],然后搜索4的附近得到6,队列变为[5,6].然后搜索5附近得到7,队列变为[6,7].搜索6的附近无节点,队列变为[7].然后搜索7的附近得到8,9,队列变为[8,9].搜索8的无节点,队列变为[9].搜索9的附近无节点,队列为空[],此次搜索则结束.

源代码在:Github 查看