DFS和BFS_bfs和dfs

一、DFS（深度优先搜素算法）

1、基本概念

深度优先搜索算法（depth first search， 简称dfs） 是一种用于遍历或搜索树或图的算法。沿着数的深度遍历树的节点，尽可能深的搜索树的分支。当节点v所在边都已被探寻或者在搜索时节点不满足条件， 搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有满足条件的所有节点被访问为止。

2、算法思路

深度优先遍历图的方法是，从图中某顶点v出发：

• （1）访问顶点v；

• （2）依次从v的未被访问的邻接节点出发，对图进行深度优先遍历，直至途中和v有路径相通的顶点都被访问；

• （3）若此图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直至图中所有顶点均被访问为止。

3、图解

实际上， DFS也是有回溯思想的， 按条件向前搜索， 以达到目标，但当搜索到某一步时，发现已经访问过过条件不满足，就退回一步重新选择该节点相邻没有被访问过的邻接节点，这就是回溯法。

如上面这张图，从1开始到2，之后到5，5没有相邻的没有被访问的节点就退回到2，访问6，再退回到2，再退回到1，接着访问3，一直这样下去。

二、BFS（广/宽度优先遍历）

1、基本概念

已知图G=(V, E)和一个源顶点s，宽度优先搜索以一种系统的方式探寻G的边，从而“发现”s所能到达的所有顶点，并计算s到所有这些顶点的距离(最少边数)，该算法同时能生成一棵根为s且包括所有可达顶点的宽度优先树。对从s可达的任意顶点v，宽度优先树中从s到v的路径对应于图G中从s到v的最短路径，即包含最小边数的路径。

2、算法思路

之所以称之为宽度优先算法，是因为算法自始至终一直通过已找到和未找到顶点之间的边界向外扩展，就是说，算法首先搜索和s距离为k的所有顶点，然后再去搜索和S距离为k+l的其他顶点。

3、图解

如上面这张图所示， 从1开始搜，有2，3，4这三个点个点，存起来，从2开始有5，6，存起来，搜3，有7，8，存起来，搜4，没有了；现在开始搜刚刚存的点，从5开始，没有，然后搜6.。。一直进行，直到找到；

实例： Leetcode

695. Max Area of Island

---

给定一个包含了一些 0 和 1 的非空二维数组 grid 。

一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)

---

DFS：

class Solution:
def dfs(self, grid, cur_i, cur_j):
    if cur_i < 0 or cur_j < 0 or cur_i == len(grid) or cur_j == len(grid[0]) or grid[cur_i][cur_j] != 1:
        return 0
    grid[cur_i][cur_j] = 0
    ans = 1
    for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
        next_i, next_j = cur_i + di, cur_j + dj
        ans += self.dfs(grid, next_i, next_j)
    return ans

def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
    ans = 0
    for i, l in enumerate(grid):
        for j, n in enumerate(l):
            ans = max(self.dfs(grid, i, j), ans)
    return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

BFS:

class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
    ans = 0
    for i, l in enumerate(grid):
        for j, n in enumerate(l):
            cur = 0
            q = collections.deque([(i, j)])
            while q:
                cur_i, cur_j = q.popleft()
                if cur_i < 0 or cur_j < 0 or cur_i == len(grid) or cur_j == len(grid[0]) or grid[cur_i][cur_j] != 1:
                    continue
                cur += 1
                grid[cur_i][cur_j] = 0
                for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                    next_i, next_j = cur_i + di, cur_j + dj
                    q.append((next_i, next_j))
            ans = max(ans, cur)
    return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

参考资料：

·（1）广度优先搜索

·（2）Leetcode-max-area-of-island

·（3）dfs和bfs

·（4）DFS(深度优先搜索算法)