一、算法概述

深度优先搜索（Depth-First Search，DFS）是一种用于遍历或搜索树或图数据结构的算法。该算法从起点出发，沿着图的深度方向尽可能深地搜索，直到到达最深处无法继续时，再回溯到上一个分支点，继续探索其他未访问的路径。DFS 是图论中最基础、最核心的算法之一。

二、核心思想

DFS 的核心思想可以概括为"一条路走到黑"：

1. 从起始节点出发，沿着一条路径不断深入探索
2. 当遇到无法继续深入的情况（如到达叶子节点、所有邻接节点均已访问）时，回溯到最近的还有未访问分支的节点
3. 重复上述过程，直到所有可达节点都被访问

这种"深入优先、不行就回退"的策略天然适合用递归实现（隐式利用系统栈），也可以用显式栈迭代实现。

三、算法步骤/伪代码

递归实现

DFS(节点 u):
    标记 u 为已访问
    处理 u（如输出、记录等）
    for 每个与 u 相邻的节点 v:
        if v 未被访问:
            DFS(v)

非递归实现（显式栈）

DFS(起点 s):
    将 s 压入栈
    while 栈非空:
        u = 栈顶元素弹出
        if u 未被访问:
            标记 u 为已访问
            处理 u
            for 每个与 u 相邻的节点 v:
                if v 未被访问:
                    将 v 压入栈

关键数据结构

• visited[] / vis[]：标记节点是否已被访问，防止重复遍历和死循环
• 递归栈（隐式）或 stack<>（显式）：维护搜索路径

四、C++ 代码实现

以下代码包含两个完整可运行的示例：全排列生成 和 图的连通分量检测。

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

// ==================== 示例1：用DFS生成1~n的全排列 ====================
class Permutation {
private:
    vector<int> path;         // 当前排列路径
    vector<bool> used;        // 标记数字是否已被使用
    vector<vector<int>> result; // 存储所有排列
    int n;

    void dfs() {
        // 终止条件：路径长度等于n，找到一个完整排列
        if ((int)path.size() == n) {
            result.push_back(path);
            return;
        }
        // 尝试将每个未使用的数字加入路径
        for (int i = 1; i <= n; ++i) {
            if (used[i]) continue;
            used[i] = true;
            path.push_back(i);
            dfs();
            // 回溯：恢复状态
            path.pop_back();
            used[i] = false;
        }
    }

public:
    vector<vector<int>> permute(int n_) {
        n = n_;
        path.clear();
        used.assign(n + 1, false);
        result.clear();
        dfs();
        return result;
    }
};

// ==================== 示例2：DFS遍历图，检测连通分量 ====================
class GraphDFS {
private:
    vector<vector<int>> adj;  // 邻接表
    vector<bool> visited;
    int V;

    // 递归DFS遍历一个连通分量
    void dfs(int u, vector<int>& component) {
        visited[u] = true;
        component.push_back(u);
        for (int v : adj[u]) {
            if (!visited[v]) {
                dfs(v, component);
            }
        }
    }

public:
    GraphDFS(int n) : V(n), adj(n), visited(n, false) {}

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);  // 无向图
    }

    // 返回所有连通分量
    vector<vector<int>> findConnectedComponents() {
        visited.assign(V, false);
        vector<vector<int>> components;
        for (int i = 0; i < V; ++i) {
            if (!visited[i]) {
                vector<int> comp;
                dfs(i, comp);
                components.push_back(comp);
            }
        }
        return components;
    }

    // 判断从s到t是否可达
    bool isReachable(int s, int t) {
        visited.assign(V, false);
        if (s < 0 || s >= V || t < 0 || t >= V) return false;
        vector<int> dummy;
        dfs(s, dummy);
        return visited[t];
    }
};

// ==================== 主函数 ====================
int main() {
    // ----- 全排列演示 -----
    cout << "========== 全排列 (n=3) ==========" << endl;
    Permutation perm;
    auto perms = perm.permute(3);
    for (auto& p : perms) {
        cout << "[ ";
        for (int x : p) cout << x << " ";
        cout << "]" << endl;
    }
    cout << "共 " << perms.size() << " 种排列" << endl;

    // ----- 图连通分量演示 -----
    cout << "\n========== 图连通分量检测 ==========" << endl;
    GraphDFS g(9); // 9个节点 0~8

    // 构建一个包含3个连通分量的图
    // 分量1：0-1-2-3
    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(2, 3);
    g.addEdge(0, 3);
    // 分量2：4-5-6
    g.addEdge(4, 5);
    g.addEdge(5, 6);
    // 分量3：7-8
    g.addEdge(7, 8);

    auto components = g.findConnectedComponents();
    cout << "连通分量个数: " << components.size() << endl;
    for (int i = 0; i < (int)components.size(); ++i) {
        cout << "分量 " << i + 1 << ": ";
        for (int v : components[i]) cout << v << " ";
        cout << endl;
    }

    cout << "0->5 可达? " << (g.isReachable(0, 5) ? "是" : "否") << endl;
    cout << "4->6 可达? " << (g.isReachable(4, 6) ? "是" : "否") << endl;

    return 0;
}

五、复杂度分析

• 时间复杂度：$\mathbf{O(V + E)}$

  • 每个节点被访问且仅被访问一次：$O(V)$
  • 每条边在其端点被访问时各被检查一次：$O(E)$
  • 对于邻接矩阵表示的图，遍历所有邻接节点需要 $O(V)$，总复杂度为 $O(V^2)$

• 空间复杂度：$\mathbf{O(V)}$

  • visited 数组：$O(V)$
  • 递归栈深度，最坏情况下（图退化为链表）为 $O(V)$

六、应用场景

场景	说明
连通性检测	判断无向图连通分量个数、有向图强连通分量
拓扑排序	基于DFS的后序遍历可以给出DAG的拓扑序
环检测	通过记录递归栈中的节点，检测有向图是否存在环
排列/组合/子集	使用回溯法生成全排列、组合、子集等
路径搜索	寻找图上从起点到终点的所有路径
迷宫求解	在网格中搜索出口
树相关问题	求树的直径、重心、最近公共祖先(LCA)的欧拉序构建等
二分图判定	交替染色，DFS验证是否冲突

七、经典例题

例题1：全排列问题

题目描述：给定一个正整数 $n$，输出 $1$ 到 $n$ 的所有全排列。

解法：使用 DFS + 回溯，每次尝试将未使用的数字放入当前位置，递归到底后收集排列并回溯。

上述代码中 Permutation 类即为完整实现。

---

例题2：岛屿数量（LeetCode 200）

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

DFS 解法（完整可运行）：

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

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

        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (grid[i][j] == '1') {
                    ++count;          // 发现新岛屿
                    dfs(grid, i, j);  // 将该岛屿所有陆地标记为已访问
                }
            }
        }
        return count;
    }

private:
    // 四个方向：上、下、左、右
    const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    void dfs(vector<vector<char>>& grid, int r, int c) {
        int rows = grid.size(), cols = grid[0].size();
        // 边界检查
        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == '0')
            return;

        grid[r][c] = '0'; // 标记为已访问（沉岛）

        // 向四个方向深入探索
        for (auto& d : dirs) {
            dfs(grid, r + d[0], c + d[1]);
        }
    }
};

int main() {
    vector<vector<char>> grid = {
        {'1', '1', '0', '0', '0'},
        {'1', '1', '0', '0', '0'},
        {'0', '0', '1', '0', '0'},
        {'0', '0', '0', '1', '1'}
    };
    Solution sol;
    cout << "岛屿数量: " << sol.numIslands(grid) << endl; // 输出: 3
    return 0;
}