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

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

在LeetCode有一题岛屿的数量题目

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

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

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

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

代码语言：javascript复制

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像栈,先进后出(回溯)

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

代码语言：javascript复制

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 像队列,先进先出,所以我们用队列来解决

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

代码语言：javascript复制

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的附近无节点,队列为空[],此次搜索则结束.

dfs 遍历 队列 搜索 算法

0 人点赞