深度优先搜索 DFS：原理、图解与 C++ 实战

一、什么是 DFS

深度优先搜索（Depth-First Search，简称 DFS）是一种用于遍历或搜索树、图等结构的算法。它的核心思想是：从起点出发，尽可能深地往一个方向走，直到走不通才回头（回溯），再选另一条路继续探索。

一句话定义
DFS = "不撞南墙不回头"——沿着一条路走到底，碰壁了就退一步换条路再走。

DFS 通常用递归实现（系统栈帮你"记住来时的路"），也可以用显式栈迭代实现。它的孪生兄弟是 BFS（广度优先），两者常被放在一起对比：

1.1 DFS vs BFS

维度	DFS（深度优先）	BFS（广度优先）
探索顺序	一条路走到底再回头	逐层向外扩展
数据结构	栈（递归 / 显式栈）	队列
空间复杂度	O(h)（h 为深度）	O(w)（w 为最大宽度）
适合求解	连通性、所有方案、路径搜索	最短路径（无权图）、层序

⚠ DFS 的两个高频坑
1. 忘记标记 visited——会死循环或重复访问
2. 回溯时忘记撤销选择——回溯法中如果不把当前选择"还原"，后续分支会出错

二、核心原理与图解

理解 DFS，关键是理解"走到尽头如何回头"。递归版 DFS 借用系统调用栈：每深入一层就压一个栈帧，回头时自动弹出。下面用图和栈模拟展示这一过程。

2.1 DFS 遍历树形图

以一棵简单的树为例，DFS 从根节点 A 出发，按"先访问当前节点，再递归访问子节点"的顺序遍历。

图 1：DFS 在树上的遍历顺序（前序）

2.2 栈模拟 DFS 过程

递归 DFS 的本质是系统调用栈在帮你管理"该回到哪里"。下面用显式栈模拟同一棵树的遍历过程：

图 2：用显式栈模拟 DFS——子节点逆序入栈保证访问顺序

2.3 回溯过程图

回溯是 DFS 的灵魂。它的核心是"做选择 → 递归 → 撤销选择"三步。下图展示回溯求全排列 [1,2,3] 的决策与回退过程：

图 3：回溯法求全排列——决策树与回退过程

2.4 复杂度分析

⏱ 时间复杂度：O(V + E)（图/树遍历）
每个节点和每条边最多访问一次。回溯法求方案时复杂度取决于方案总数，如全排列是 O(n!)，子集是 O(2^n)。

💾 空间复杂度：O(h)（递归栈深度）
h 为搜索树最大深度。最坏情况退化成 O(V)（链状图）。二维网格 DFS 中是 O(行×列) 最坏。

三、通用模板

下面给出 DFS 的两种核心写法：递归版（最常用）和栈迭代版（避免栈溢出）。再加一个回溯模板用于求所有方案。

// ============= 模板 1：递归版 DFS（图/网格遍历）=============
const int dx[] = {-1, 1, 0, 0};  // 上下左右四个方向
const int dy[] = {0, 0, -1, 1};

void dfs(vector<vector<char>>& grid,
        vector<vector<bool>>& visited,
        int x, int y) {
    int m = grid.size(), n = grid[0].size();
    // 边界 + 已访问 + 非目标格子 → 返回
    if (x < 0 || x >= m || y < 0 || y >= n) return;
    if (visited[x][y] || grid[x][y] == '0') return;

    visited[x][y] = true;  // 标记访问

    // 向四个方向递归
    for (int i = 0; i < 4; ++i) {
        dfs(grid, visited, x + dx[i], y + dy[i]);
    }
}

// ============= 模板 2：栈迭代版 DFS（避免递归栈溢出）=============
void dfsIterative(vector<vector<char>>& grid, int sx, int sy) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    stack<pair<int,int>> st;

    st.push({sx, sy});
    while (!st.empty()) {
        auto [x, y] = st.top(); st.pop();
        if (x < 0 || x >= m || y < 0 || y >= n) continue;
        if (visited[x][y] || grid[x][y] == '0') continue;

        visited[x][y] = true;
        for (int i = 0; i < 4; ++i) {
            st.push({x + dx[i], y + dy[i]});
        }
    }
}

// ============= 模板 3：回溯法模板（求所有方案）=============
void backtrack(vector<int>& path, vector<bool>& used,
              const vector<int>& nums,
              vector<vector<int>>& ans) {
    if (path.size() == nums.size()) {  // 触发结束条件
        ans.push_back(path);
        return;
    }
    for (int i = 0; i < nums.size(); ++i) {
        if (used[i]) continue;
        // 做选择
        path.push_back(nums[i]);
        used[i] = true;
        // 递归
        backtrack(path, used, nums, ans);
        // 撤销选择（回溯）
        path.pop_back();
        used[i] = false;
    }
}

模板三要点
1. 递归版要标记 visited——进入递归后立即标记，避免重复访问
2. 栈迭代版要"弹出即访问"——弹出栈顶后立即标记，否则同一节点会被多次入栈
3. 回溯法要"撤销选择"——递归返回前必须把 path 和 used 恢复，否则后续分支受污染

四、示例一：岛屿数量（LeetCode 200）

题目：给定一个 '1'（陆地）和 '0'（水）组成的二维网格，计算岛屿的数量。岛屿是被水包围的一块连通陆地（上下左右相邻视为连通）。

4.1 思路：DFS 染色

遍历每个格子，遇到 '1' 就发现了一个新岛屿，计数 +1，然后从该格出发 DFS 把整个岛屿"染色"（改成 '0'），避免重复计数。

图 4：岛屿数量——DFS 把每个岛屿染色后统计

4.2 C++ 代码

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

class Solution {
    // 方向数组：上下左右
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    int m, n;

    // DFS 把 (x,y) 所在岛屿全部染成 '0'
    void dfs(vector<vector<char>>& grid, int x, int y) {
        // 越界 / 是水 / 已访问（染成 '0' 即视为已访问）→ 返回
        if (x < 0 || x >= m || y < 0 || y >= n) return;
        if (grid[x][y] == '0') return;

        grid[x][y] = '0';  // 染色：陆地变水，相当于标记 visited

        // 向四个方向扩展
        for (int i = 0; i < 4; ++i) {
            dfs(grid, x + dx[i], y + dy[i]);
        }
    }

public:
    int numIslands(vector<vector<char>>& grid) {
        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;
    }
};

💡 一个巧妙的优化
这题直接修改原网格作为 visited 标记（'1' → '0'），省下一个 visited 数组的空间。如果题目要求不能修改原数据，再单独开 vector<vector<bool>> visited。

五、示例二：岛屿的最大面积（LeetCode 695）

题目：给定一个非空 0-1 二维数组，1 表示陆地，0 表示水。岛屿是上下左右连通的 1。返回最大岛屿的面积（即 1 的个数）。没有岛屿则返回 0。

5.1 思路：DFS 累加面积

和"岛屿数量"几乎一样，只是这次 DFS 不光要染色，还要返回当前岛屿的面积。每个格子贡献 1，加上四个方向 DFS 的返回值。

图 5：岛屿最大面积——DFS 返回值累加得每个岛屿面积

5.2 C++ 代码

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

class Solution {
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    int m, n;

    // DFS 返回从 (x,y) 出发能访问到的岛屿面积
    int dfs(vector<vector<int>>& grid, int x, int y) {
        if (x < 0 || x >= m || y < 0 || y >= n) return 0;
        if (grid[x][y] == 0) return 0;

        grid[x][y] = 0;  // 染色，防止重复计数

        // 当前格子 1 + 四个方向的面积
        int area = 1;
        for (int i = 0; i < 4; ++i) {
            area += dfs(grid, x + dx[i], y + dy[i]);
        }
        return area;
    }

public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
        int maxArea = 0;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    maxArea = max(maxArea, dfs(grid, i, j));
                }
            }
        }
        return maxArea;
    }
};

💡 与"岛屿数量"的对比
唯一区别：DFS 的返回值。岛屿数量中 DFS 返回 void（只染色），岛屿最大面积中 DFS 返回 int（累加面积）。骨架完全一样，"DFS 函数返回什么"是这类题目的核心变化点。

六、示例三：全排列（LeetCode 46）

题目：给定一个没有重复数字的数组 nums，返回其所有可能的全排列。可以按任意顺序返回。

6.1 思路：回溯法

全排列是回溯法的经典应用。维护一个 path 表示当前已选元素，一个 used 数组标记哪些元素已用过。每一轮从所有未用过的元素里选一个加入 path，递归到下一层；递归返回后撤销选择，换下一个元素试。

图 6：全排列回溯决策树——6 个叶子对应 6 个排列

6.2 C++ 代码

#include <vector>
using namespace std;

class Solution {
    vector<vector<int>> ans;
    vector<int> path;
    vector<bool> used;

    void backtrack(const vector<int>& nums) {
        // 结束条件：path 已包含所有元素
        if (path.size() == nums.size()) {
            ans.push_back(path);
            return;
        }

        // 遍历所有候选元素
        for (int i = 0; i < nums.size(); ++i) {
            if (used[i]) continue;  // 已用过，跳过

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

            // ===== 递归进入下一层 =====
            backtrack(nums);

            // ===== 撤销选择（回溯）=====
            path.pop_back();
            used[i] = false;
        }
    }

public:
    vector<vector<int>> permute(vector<int>& nums) {
        used.assign(nums.size(), false);
        backtrack(nums);
        return ans;
    }
};

⚠ 回溯法最易错点：撤销选择
path.pop_back() 和 used[i] = false 这两行必须在递归返回之后执行，且无论递归里发生什么都要执行。如果忘了撤销，path 会越积越长，used 永远是 true，后续分支全部失效。新手常把这两行写到 if 里或漏写，要特别小心。

💡 也可以用 swap 写法（空间更省）
全排列还有一种"原地交换"写法：维护一个指针 first，把它和后面每个位置交换后递归。这样不需要 used 数组，但思路更绕。掌握上面的 used 版本已足够应对大多数回溯题。

七、总结与适用场景

DFS 核心要点

维度	要点
本质	一条路走到底再回溯，借用递归栈管理"来路"
时间复杂度	图/树遍历 O(V+E)；回溯求方案取决于方案数（如 n!, 2^n）
空间复杂度	O(h)，h 为搜索深度；最坏 O(V)
识别信号	连通性问题、岛屿/区域填充、所有方案枚举、路径搜索
关键技巧	标记 visited、回溯撤销选择、方向数组、剪枝

典型题目清单

LeetCode 200：岛屿数量（网格 DFS 染色）
LeetCode 695：岛屿的最大面积（DFS 返回值累加）
LeetCode 46：全排列（回溯基础）
LeetCode 47：全排列 II（含重复元素，需剪枝）
LeetCode 39/40/216：组合总和（回溯 + 剪枝）
LeetCode 78/90：子集（回溯另一种形态）
LeetCode 79：单词搜索（网格 + 路径回溯）
LeetCode 130：被围绕的区域（DFS 染色 + 边界反向思维）
LeetCode 133：克隆图（DFS 遍历 + 哈希记录）
LeetCode 51：N 皇后（回溯经典）

🎯 记忆口诀
"走到深处才回头，标记 visited 莫忘了；回溯三步做撤回，方向数组循环跑。"
第一句讲 DFS 的核心节奏，第二句强调标记访问，第三句是回溯法的"做选择→递归→撤销"，第四句提醒用方向数组简化四方向遍历。