当神不再是我们的信仰,那么信仰自己吧,努力让自己变好,不辜负自己的信仰!

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

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


LeetCode有一题岛屿的数量题目

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


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

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

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

  • 这一题的答案不管用DFS还是BFS都是1
  1. DFS搜索的顺序总是先往同一个方向发展,直到尽头.
  2. 然后尽头节点发展其他方向,直至所有方向.
  3. 然后回溯到上一个可以发展的节点
  4. DFS像栈,先进后出(回溯)

* 假设顺序是 ↑↓←→(上下左右)
* 那么这个岛屿遍历的顺序是:

  • 1开始,上方向是边界,所以向下搜索一直到4,4到了尽头,而且其他方向没有岛屿,然后回溯到2,2的上下已经搜索过,所以往右边搜索得到5,5向上搜索得到6然后回溯到5,再向右搜索得到7,7的左边已经搜索过,所以向下搜索得到8,然后8附近没有岛屿,回溯搜索到9,至此结束.

  1. BFS搜索的顺序总是先往附近节点发展
  2. 当发展完附近的之后,然后再按附近的顺序再发展附近的节点
  3. BFS 像队列,先进先出,所以我们用队列来解决

* 假设顺序是 ↑↓←→(上下左右)
* 那么这个岛屿遍历的顺序是:

  • (每次搜索接受后丢掉当前节点)从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 查看

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注