（DFS）深度优先搜索(不喜勿喷)求赞

userId_undefined
入
时空双修者题解仙人

2026-06-07 19:42:05

发布于：浙江

3阅读
0回复
0点赞

一、深度优先搜索（DFS）定义
深度优先搜索（Depth-First Search，DFS） 是一种回溯式的搜索算法，核心思想：不撞南墙不回头。
它会沿着一条路径一直往下走，直到走到尽头（无法继续前进），再回溯到上一个节点，尝试其他未走过的路径，直到遍历完所有可能的路径。
可以用树 / 图的遍历理解：从起点出发，优先访问子节点，直到叶子节点，再回退找其他分支。
DFS 本质是递归（也可用栈手动实现），利用递归的 “调用 - 回溯” 特性完成搜索。

二、DFS 的核心用处
遍历：树 / 图的深度遍历（前序 / 中序 / 后序遍历）
路径查找：找两点之间的所有路径、最短路径（无权重）
组合 / 排列问题：生成所有子集、全排列、组合数
连通性问题：判断图是否连通、找连通分量
棋盘 / 网格问题：迷宫搜索、岛屿数量、单词搜索
回溯类问题：N 皇后、解数独、括号生成

三、DFS 常见题型分类
基础遍历：树 / 图遍历、网格遍历
组合与排列：子集、全排列、组合总和
网格搜索：岛屿数量、迷宫求解、单词搜索
回溯剪枝：N 皇后、解数独、目标和
连通性 / 区域问题：连通块计数、染色问题

四、DFS 通用模板（C++）

  1. 递归版 DFS（最常用，代码简洁）
// 通用模板：参数根据题目调整（当前位置、访问标记、结果、输入数据等）
void dfs(参数列表) {
    // 1. 递归终止条件（边界/结束条件）
    if (满足终止条件) {
        记录结果/返回;
        return;
    }

    // 2. 标记当前节点已访问（避免重复走，图/网格必加）
    visited[当前节点] = true;

    // 3. 遍历所有可能的方向/分支（子节点、上下左右、选择项）
    for (遍历所有可选分支) {
        if (该分支有效 && 未访问) {
            dfs(下一个状态); // 递归深入
        }
    }

    // 4. 回溯：取消标记（如果需要遍历所有路径，必须回溯！）
    visited[当前节点] = false;
}
  1. 栈手动实现 DFS（非递归，避免递归栈溢出）
void dfs_stack(起始节点) {
    stack<节点类型> st;
    st.push(起始节点);
    visited[起始节点] = true;

    while (!st.empty()) {
        节点 = st.top();
        st.pop();

        处理当前节点;

        for (所有相邻节点) {
            if (有效 && 未访问) {
                visited[相邻节点] = true;
                st.push(相邻节点);
            }
        }
    }
}

五、经典 DFS 例题 + 解题思路
例题 1：二叉树的前序遍历（基础遍历）
题目：给定二叉树，返回前序遍历结果（根→左→右）。
解题思路：
1.终止条件：当前节点为空，直接返回
2.先访问根节点
3.递归遍历左子树
4.递归遍历右子树

#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

vector<int> res;
// DFS 前序遍历
void dfs(TreeNode* root) {
    if (!root) return; // 终止：节点为空
    res.push_back(root->val); // 访问根
    dfs(root->left); // 左子树
    dfs(root->right); // 右子树
}

vector<int> preorderTraversal(TreeNode* root) {
    res.clear();
    dfs(root);
    return res;
}

题 2：岛屿数量（网格搜索，高频）
题目：给定二维网格，1 是陆地，0 是水，求岛屿数量（上下左右连通为一个岛屿）。
解题思路：
1.遍历网格每一个格子
2.遇到陆地（1）且未被访问：岛屿数量 + 1，启动 DFS
3.DFS 把当前陆地及所有连通的陆地标记为已访问（染色为 0）
4.终止条件：超出网格边界 或 当前是水

#include <vector>
using namespace std;

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty()) return 0;
        int m = grid.size(), n = grid[0].size();
        int count = 0;

        // 遍历所有格子
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    count++; // 发现新岛屿
                    dfs(grid, i, j); // 淹没整个岛屿
                }
            }
        }
        return count;
    }

    // DFS：将连通的陆地全部染色为0
    void dfs(vector<vector<char>>& grid, int i, int j) {
        // 终止条件：越界 或 不是陆地
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == '0') {
            return;
        }

        grid[i][j] = '0'; // 标记已访问

        // 上下左右四个方向
        dfs(grid, i+1, j);
        dfs(grid, i-1, j);
        dfs(grid, i, j+1);
        dfs(grid, i, j-1);
    }
};

例题 3：全排列（组合排列，回溯）
题目：给定不含重复数字的数组，返回所有可能的全排列。
解题思路：
1.用 DFS 枚举每一个位置的数字
2.用 visited 标记已选数字，避免重复
3.路径长度等于数组长度时，记录结果
4.回溯：取消选择，尝试下一个数字

#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<bool> visited;

    vector<vector<int>> permute(vector<int>& nums) {
        res.clear();
        path.clear();
        visited.assign(nums.size(), false);
        dfs(nums);
        return res;
    }

    void dfs(vector<int>& nums) {
        // 终止：路径满了，保存结果
        if (path.size() == nums.size()) {
            res.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (visited[i]) continue; // 已选过，跳过

            visited[i] = true; // 选择
            path.push_back(nums[i]);

            dfs(nums); // 递归

            path.pop_back(); // 回溯：撤销选择
            visited[i] = false;
        }
    }
};

例题 4：子集（组合问题）
题目：给定数组，返回所有可能的子集（包含空集，不重复）。
解题思路：
1.每一步有两个选择：选当前数字 / 不选
2.DFS 遍历所有选择，记录每一个中间状态
3.终止条件：遍历完所有数字

#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    vector<vector<int>> subsets(vector<int>& nums) {
        res.clear();
        path.clear();
        dfs(nums, 0);
        return res;
    }

    // start：从第几个数字开始选
    void dfs(vector<int>& nums, int start) {
        // 记录所有中间状态（子集）
        res.push_back(path);

        for (int i = start; i < nums.size(); i++) {
            path.push_back(nums[i]); // 选
            dfs(nums, i + 1); // 往后选，不回头
            path.pop_back(); // 不选，回溯
        }
    }
};

六、DFS 核心要点总结
三大要素：
递归终止条件
状态标记（访问 / 选择）
回溯（撤销操作）
适用场景：需要遍历所有可能、找路径、组合排列、连通区域
优点：代码简洁，适合深度探索
缺点：深度过大会栈溢出（可用非递归栈优化）
剪枝：提前排除无效路径，大幅提升效率（回溯题必用）

总结
DFS = 递归深入 + 回溯，核心是一条路走到底再回头
通用模板：终止条件 → 标记 → 遍历分支 → 回溯
高频题型：网格搜索（岛屿）、排列组合、树遍历、路径查找
做题步骤：找终止条件 → 定方向 / 选择 → 加标记 → 写回溯

userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论