详解深度优先搜索（DFS，Depth-First Search）_深度优先搜索(depth-first search,dfs) csdn @归途无路

深度优先搜索（DFS，Depth-First Search）是一种用于遍历或搜索树或图的算法。与它对应的算法是宽度优先搜索（BFS，Breadth-First Search）。DFS使用递归或堆栈的方式实现搜索过程，并遵循深度优先原则探索可能的路径。

基本思想

深度优先搜索在进行搜索时，尽可能深地搜索图的分支。当节点v的所有出去的边都已被探测过，搜索将回溯到发现节点v的那条边的起始节点。这个过程一直进行到已发现从源节点可达的所有节点为止。

如果存在未发现的节点，那么深度优先搜索将从一个未发现的节点开始新的搜索。该算法会终止当所有节点都被发现。

DFS可以在搜索过程中解决许多问题，当需要检查所有可能的解决方案时，DFS是一个理想的选择，常见于解决递归问题和回溯算法。

伪代码

DFS(node) {  
    标记 node 为已探索
    对于 node 的每个未探索的邻居 neighbor，调用 DFS(neighbor)
}
1
2
3
4

开始于：

对于每个未探索的节点 node，调用 DFS(node)
1

DFS 经典问题及其C++代码

接下来，我们将介绍一些经典的使用深度优先搜索（DFS）解决的问题。

问题1：二叉树的最大深度

问题描述

给你一个二叉树的根节点root，找出其中最深的叶子节点，返回它们深度。

解题思路

使用DFS来访问每个节点，并沿途记录当前的深度，比较不同分支的深度，返回最大值。

// 二叉树节点的定义
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
};

int maxDepth(TreeNode* root) {
    if (!root) {
        return 0; // 空节点深度为0
    }
    int leftDepth = maxDepth(root->left); // 左子树的深度
    int rightDepth = maxDepth(root->right); // 右子树的深度
    return 1 + max(leftDepth, rightDepth); // 当前节点的深度 = 左/右子树深度的较大者 + 1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

问题2：生成有效的括号组合

问题描述

给定一个数字n，生成所有可能的且有效的括号组合。

解题思路

在递归每一步中，我们维护两个变量，left 和 right 分别为已放置的左括号和右括号的数量。只有在知道序列仍然有效时（即不会形成如"())"这样的序列），我们才添加一个左括号或右括号。

void dfs(vector<string>& result, string& current, int left, int right, int n) {
    if (current.size() == 2 * n) {
        result.push_back(current);
        return;
    }
    
    if (left < n) {
        current.push_back('(');
        dfs(result, current, left + 1, right, n);
        current.pop_back();
    }
    
    if (right < left) {
        current.push_back(')');
        dfs(result, current, left, right + 1, n);
        current.pop_back();
    }
}

vector<string> generateParenthesis(int n) {
    vector<string> result;
    string current;
    dfs(result, current, 0, 0, n);
    return result;
}
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

问题3：岛屿数量

问题描述

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，且每座岛屿只能由水平方向或垂直方向上相邻的陆地连接形成。

解题思路

遍历整个网格，当我们遇到 ‘1’，我们会启动DFS并沉没（通过将 ‘1’ 变为 ‘0’）与之相连的所有陆地，岛屿数量加1。遍历完整个网格后，返回岛屿数量。

void sinkIsland(vector<vector<char>>& grid, int x, int y) {
    // 超出边界或者已经是水域
    if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] == '0') {
        return;
    }

    // 将当前的 '1' 变为 '0'
    grid[x][y] = '0';

    // 沉没与当前位置相连的陆地
    sinkIsland(grid, x + 1, y);
    sinkIsland(grid, x - 1, y);
    sinkIsland(grid, x, y + 1);
    sinkIsland(grid, x, y - 1);
}

int numIslands(vector<vector<char>>& grid) {
    if (grid.empty()) return 0;
    
    int num_islands = 0;
    for (int i = 0; i < grid.size(); ++i) {
        for (int j = 0; j < grid[0].size(); ++j) {
            if (grid[i][j] == '1') {
                ++num_islands;
                sinkIsland(grid, i, j); // 沉没发现的岛屿
            }
        }
    }

    return num_islands;
}
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

问题4：全排列

问题描述

给定一个没有重复数字的序列，返回其所有可能的全排列。

解题思路

在每一步中，我们考虑那些还没有被选择的数字，将一个数字添加到当前排列中，然后递归调用，直到所有数字都被选中。然后回溯，撤销选择，继续尝试其他数字。

void permuteRec(vector<int>& nums, vector<vector<int>>& result, int start) {
    if (start >= nums.size()) {
        result.push_back(nums); // 添加当前排列到结果列表中
        return;
    }

    for (int i = start; i < nums.size(); ++i) {
        swap(nums[start], nums[i]);               // 交换数字
        permuteRec(nums, result, start + 1);      // 递归调用
        swap(nums[start], nums[i]);               // 回溯，撤销交换
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> result;
    permuteRec(nums, result, 0);
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

问题5：组合总和

问题描述

给定一个无重复元素的数组和一个目标数target，找出数组中所有可以使数字和为target的组合。数组中的数字可以无限制重复被选取。

解题思路

可以通过DFS来在每个节点考虑选择当前数字或者不选择当前数字，然后进一步递归这两个选择。

void combinationSumRec(vector<int>& candidates, int target, vector<int>& current,
                       vector<vector<int>>& result, int start) {
    if (target == 0) {
        result.push_back(current); // 找到一个有效解
        return;
    }

    for (int i = start; i < candidates.size() && target - candidates[i] >= 0; ++i) {
        current.push_back(candidates[i]);                                    // 选择当前数字
        combinationSumRec(candidates, target - candidates[i], current, result, i); // 递归调用
        current.pop_back();                                                  // 回溯，撤销选择
    }
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> result;
    vector<int> current;
    combinationSumRec(candidates, target, current, result, 0);
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

以上问题及解法展示了DFS算法在不同场景下的强大应用，通过递归和回溯，DFS能够高效地找到问题的有效解。在实际编程中，要注意递归的终止条件和避免无限递归的情况，也要处理好状态回溯，确保解的空间被正确探索。

如果你想更深入地了解人工智能的其他方面，比如机器学习、深度学习、自然语言处理等等，也可以点击这个链接，我按照如下图所示的学习路线为大家整理了100多G的学习资源，基本涵盖了人工智能学习的所有内容，包括了目前人工智能领域最新顶会论文合集和丰富详细的项目实战资料，可以帮助你入门和进阶。

链接： 人工智能交流群【最新顶会与项目实战】（点击跳转）