深度优先搜索算法 DFS

2022-05-16 约 2400 字预计阅读 5 分钟

深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。这种算法不会根据图的结构等信息调整执行策略[来源请求]。

深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如无权最长路径问题等等。

平均时间复杂度 $O(b^m)$
空间复杂度 $O(bm)$
b 分支系数 m 图的最大深度

演算方法

首先将根节点放入stack中。
从stack中取出第一个节点，并检验它是否为目标。
1. 如果找到目标，则结束搜寻并回传结果。
2. 否则将它某一个尚未检验过的直接子节点加入stack中。
重复步骤2。
如果不存在未检测过的直接子节点。
1. 将上一级节点加入stack中。
2. 重复步骤2。
重复步骤4。
若stack为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。

「DFS 算法」和「回溯算法」其实是同一个概念，本质上都是一种暴力穷举算法
「DFS 算法」其实就是在树的遍历过程中增加了「决策」。

框架提出

当我们站在回溯树的一个节点上，你只需要思考 3 个问题：

路径：已经做出的选择
选择列表：当前可以做的选择
结束条件：到达决策树底层，无法再做选择的条件

基于这三个问题，给出伪代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

全排列

排列树

要得到所有的全排列组合，无非就是得到所有从根节点到叶子结点的路径！

问题一：由于这是一颗抽象出来的树，叶子节点并没有和树一样的特征，如何判断到达了叶子节点?

根据路径的长度判断是否结束

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


int[] nums = {1, 2, 3};
List<Integer> path = new ArrayList<>();
List<List<Integer>> result = new ArrayList<>();
public void backtrack(int[] nums) {
    // 判断：结束条件
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path));
        return ;
    }
    for (int i = 0; i < nums.length; i++) {
        // 先序：首次进入节点，添加到「路径」中
        path.add(nums[i]);
        // 递归
        backtrack(nums);
        // 后续：即将离开节点，从「路径」中除去
        path.remove(path.size() - 1);
    }
}

问题二：对于上述结果，存在元素重复使用的情况，如何避免这种情况呢？？(如上图红色标注的分支均为不符合条件的情况)

新增一个used[]数组，记录元素使用情况

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


int[] nums = {1, 2, 3};
boolean[] used[] = new boolean[nums.length];
List<Integer> path = new ArrayList<>();
List<List<Integer>> result = new ArrayList<>();
public void backtrack(int[] nums) {
    // 判断：结束条件
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path));
        return ;
    }
    for (int i = 0; i < nums.length; i++) {
        // 如果使用过了，则直接跳过
        if (used[i]) continue;
        // 先序：首次进入节点，添加到「路径」中
        path.add(nums[i]);
        // 标记使用
        used[i] = true;
        // 递归
        backtrack(nums);
        // 后续：即将离开节点，从「路径」中除去
        path.remove(path.size() - 1);
        // 取消标记
        used[i] = false;
    }
}

岛屿问题

岛屿问题是一个图的问题，本质也是使用 DFS 算法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


// 递归：「当前节点」「该做什么」「什么时候做」
// FloodFill：如果当前位置是岛屿，则填充为海水
//   - 充当了 visited[] 的作用
private void dfs(int[][] grid, int i, int j) {
    int m = grid.length;
    int n = grid[0].length;
    // 越界检查
    if (i < 0 || i >= m || j < 0 || j >= n) return ;
    // 如果是海水
    if (grid[i][j] == 0) return ;
    // 否则：1 -> 0
    grid[i][j] = 0;
    // 递归处理上下左右
    dfs(grid, i - 1, j); // 上
    dfs(grid, i + 1, j); // 下
    dfs(grid, i, j - 1); // 左
    dfs(grid, i, j + 1); // 右
}

岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 ‘0’ 或 ‘1’

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


class Solution {
    void dfs(char[][] grid, int r, int c) {
        int nr = grid.length;
        int nc = grid[0].length;

        if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
            return;
        }

        grid[r][c] = '0';
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    dfs(grid, r, c);
                }
            }
        }

        return num_islands;
    }
}

复杂度分析

时间复杂度：$O(MN)$，其中 $M$ 和 $N$ 分别为行数和列数。
空间复杂度：$O(MN)$，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 $MN$。

被围绕的岛屿

给你一个 $m \times n$ 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

任何边界上的 O 都不会被填充为 X。我们可以想到，所有的不被包围的 O 都直接或间接与边界上的 O 相连。我们可以利用这个性质判断 O 是否在边界上，具体地说：

对于每一个边界上的 O，我们以它为起点，标记所有与它直接或间接相连的字母 O；
最后我们遍历这个矩阵，对于每一个字母：
- 如果该字母被标记过，则该字母为没有被字母 X 包围的字母 O，我们将其还原为字母 O；
- 如果该字母没有被标记过，则该字母为被字母 X 包围的字母 O，我们将其修改为字母 X。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


class Solution {
    int n, m;

    public void solve(char[][] board) {
        n = board.length;
        if (n == 0) {
            return;
        }
        m = board[0].length;
        // 选择出与岸边相连的岛屿并标记为 A
        for (int i = 0; i < n; i++) {
            dfs(board, i, 0);
            dfs(board, i, m - 1);
        }
        for (int i = 1; i < m - 1; i++) {
            dfs(board, 0, i);
            dfs(board, n - 1, i);
        }
        // 把内部封闭的岛屿全部置为 X，把 A 置为 O
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'A') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }

    public void dfs(char[][] board, int x, int y) {
        if (x < 0 || x >= n || y < 0 || y >= m || board[x][y] != 'O') {
            return;
        }
        board[x][y] = 'A';
        dfs(board, x + 1, y);
        dfs(board, x - 1, y);
        dfs(board, x, y + 1);
        dfs(board, x, y - 1);
    }
}

BFS DFS

BFS 递归。可以想想二叉树中如何递归的进行层序遍历。 BFS 非递归。一般用队列存储。 DFS 递归。最常用，如二叉树的先序遍历。 DFS 非递归。一般用 stack。

附录

https://zh.wikipedia.org/zh-cn/深度优先搜索

目录