深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。在C++中实现DFS时，分析其时间复杂度有助于我们了解算法的性能，以下是详细的分析方法：

1. 基本概念

时间复杂度描述了算法的运行时间随输入规模增长的变化趋势，通常用大O表示法来表示。在分析DFS的时间复杂度时，主要考虑的是算法在最坏情况下需要执行的操作次数。

2. 不同场景下的时间复杂度分析

树的DFS

• 树的结构特点：树是一种无向无环图，每个节点有零个或多个子节点。假设树的节点数为 (n)。
• 递归实现的DFS：在对树进行深度优先搜索时，通常会从根节点开始，递归地访问每个节点及其子节点。由于每个节点只会被访问一次，因此对于树的DFS，其时间复杂度为 (O(n))。 以下是一个简单的树节点结构体和DFS遍历的C++代码示例：

#include <iostream>
#include <vector>

// 定义树节点结构体
struct TreeNode {
    int val;
    std::vector<TreeNode*> children;
    TreeNode(int x) : val(x) {}
};

// 树的DFS函数
void dfs(TreeNode* node) {
    if (node == nullptr) return;
    // 处理当前节点，这里简单打印节点值
    std::cout << node->val << " ";
    // 递归访问所有子节点
    for (TreeNode* child : node->children) {
        dfs(child);
    }
}

分析：在上述代码中，每个节点都恰好被访问一次，所以无论树的形状如何（如二叉树、多叉树），时间复杂度都是 (O(n))，其中 (n) 是树中节点的数量。

图的DFS

• 图的表示方法：图可以用邻接矩阵或邻接表来表示。设图的节点数为 (V)，边数为 (E)。
• 邻接矩阵表示的图：邻接矩阵是一个 (V\times V) 的二维数组，其中 matrix[i][j] 表示节点 (i) 和节点 (j) 之间是否有边相连。在使用邻接矩阵进行DFS时，对于每个节点，需要遍历矩阵的一行来查找其所有邻接节点，因此时间复杂度为 (O(V^2))。 以下是使用邻接矩阵进行图的DFS的C++代码示例：

#include <iostream>
#include <vector>

const int MAXN = 100;
std::vector<bool> visited(MAXN, false);

// 邻接矩阵表示的图的DFS函数
void dfsMatrix(int graph[MAXN][MAXN], int node, int V) {
    visited[node] = true;
    std::cout << node << " ";
    for (int i = 0; i < V; ++i) {
        if (graph[node][i] == 1 && !visited[i]) {
            dfsMatrix(graph, i, V);
        }
    }
}

分析：在上述代码中，对于每个节点，都需要遍历矩阵的一行（长度为 (V)）来查找其邻接节点，总共有 (V) 个节点，所以时间复杂度为 (O(V^2))。

• 邻接表表示的图：邻接表是一个数组，数组的每个元素是一个链表，链表中存储了该节点的所有邻接节点。在使用邻接表进行DFS时，对于每个节点，只需要遍历其邻接表中的节点，因此时间复杂度为 (O(V + E))。 以下是使用邻接表进行图的DFS的C++代码示例：

#include <iostream>
#include <vector>

std::vector<bool> visited;

// 邻接表表示的图的DFS函数
void dfsList(const std::vector<std::vector<int>>& graph, int node) {
    visited[node] = true;
    std::cout << node << " ";
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfsList(graph, neighbor);
        }
    }
}

分析：在上述代码中，对于每个节点，会遍历其邻接表中的所有邻接节点。所有节点的邻接表的总长度为边数 (E)，而每个节点只会被访问一次，所以时间复杂度为 (O(V + E))。

棋盘类问题的DFS

• 棋盘的特点：棋盘类问题通常可以看作是一个二维网格，每个格子可以看作是一个节点，相邻的格子之间有边相连。设棋盘的行数为 (m)，列数为 (n)。
• 典型问题分析：例如在一个 (m\times n) 的棋盘中进行DFS搜索路径，最坏情况下可能需要遍历棋盘上的每个格子，因此时间复杂度为 (O(m\times n))。 以下是一个简单的棋盘DFS示例：

#include <iostream>
#include <vector>

const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
std::vector<std::vector<bool>> visited;

// 棋盘的DFS函数
void dfsBoard(const std::vector<std::vector<int>>& board, int x, int y) {
    int m = board.size();
    int n = board[0].size();
    visited[x][y] = true;
    std::cout << "(" << x << ", " << y << ") ";
    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
            dfsBoard(board, nx, ny);
        }
    }
}

分析：在上述代码中，每个格子最多被访问一次，棋盘上总共有 (m\times n) 个格子，所以时间复杂度为 (O(m\times n))。

3. 影响时间复杂度的其他因素

• 剪枝操作：在DFS过程中，如果能够提前判断某些路径不可能得到最优解或合法解，就可以提前终止对这些路径的搜索，这就是剪枝操作。剪枝操作可以显著减少搜索的节点数量，从而降低时间复杂度。例如在一些组合问题中，通过剪枝可以避免不必要的递归调用。
• 记忆化搜索：当DFS过程中存在大量重复的子问题时，可以使用记忆化搜索来避免重复计算。通过使用一个数组或哈希表来记录已经计算过的子问题的结果，在下次遇到相同的子问题时，直接从记录中获取结果，而不需要重新计算，从而提高算法的效率。

综上所述，分析C++深度优先搜索的时间复杂度需要根据具体的问题场景和数据结构来进行，主要考虑节点数、边数等因素，同时还要考虑剪枝和记忆化搜索等优化操作对时间复杂度的影响。

以下是一份从0开始的C++深度优先搜索（DFS）教程，结合经典OJ题目，帮助您快速入门：

一、DFS基础概念

1. 核心思想

• “一条路走到黑”：从起点出发，尽可能深入探索每一条路径，直到无法继续（死胡同），然后回溯到上一个节点，尝试其他路径。
• 递归实现：通过递归函数模拟回溯过程，利用函数调用栈自动管理路径状态。

2. 典型场景

• 全排列、组合问题
• 迷宫路径、岛屿数量统计
• 树/图的遍历
• 棋盘问题（如N皇后）

二、DFS实现步骤

以迷宫问题为例，演示DFS流程：

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

// 迷宫地图（0表示通路，1表示障碍）
vector<vector<int>> maze = {
    {0, 1, 0, 0},
    {0, 1, 0, 1},
    {0, 0, 0, 0}
};
int rows = maze.size(), cols = maze[0].size();
vector<vector<bool>> visited(rows, vector<bool>(cols, false)); // 记录访问状态

// 四个方向：右、下、左、上
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

bool dfs(int x, int y) {
    if (x == rows - 1 && y == cols - 1) return true; // 到达终点
    visited[x][y] = true; // 标记当前节点已访问
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        // 检查边界、是否为通路、是否未访问
        if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && 
            maze[nx][ny] == 0 && !visited[nx][ny]) {
            if (dfs(nx, ny)) return true; // 递归探索
        }
    }
    visited[x][y] = false; // 回溯：取消当前节点标记
    return false;
}

int main() {
    if (dfs(0, 0)) cout << "找到路径！";
    else cout << "无解！";
    return 0;
}

关键点解析：

1. 递归终止条件：到达终点时返回成功。
2. 状态标记：使用visited数组避免重复访问。
3. 回溯：递归返回前取消当前节点标记，以便其他路径可以再次访问。

三、OJ经典题目详解

题目1：全排列（LeetCode 46）

题目描述：给定数组nums，返回所有可能的全排列。

思路：

• 递归选择每个位置的数字，使用标记数组避免重复。
• 当路径长度等于数组长度时，记录结果。

代码：

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

void dfs(vector<int>& nums, vector<int>& path, vector<bool>& used, vector<vector<int>>& res) {
    if (path.size() == nums.size()) {
        res.push_back(path);
        return;
    }
    for (int i = 0; i < nums.size(); i++) {
        if (!used[i]) {
            used[i] = true;
            path.push_back(nums[i]);
            dfs(nums, path, used, res);
            path.pop_back(); // 回溯
            used[i] = false;
        }
    }
}

题目2：N皇后（LeetCode 51）

题目描述：在n×n棋盘上放置n个皇后，使其互不攻击。

思路：

• 逐行放置皇后，检查列和对角线是否冲突。
• 使用三个集合记录已占用的列、正斜线（行+列）、反斜线（行-列）。

代码：

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> res;
    vector<string> board(n, string(n, '.'));
    set<int> cols, diag1, diag2;
    dfs(0, board, cols, diag1, diag2, res);
    return res;
}

void dfs(int row, vector<string>& board, set<int>& cols, 
         set<int>& diag1, set<int>& diag2, vector<vector<string>>& res) {
    if (row == board.size()) {
        res.push_back(board);
        return;
    }
    for (int col = 0; col < board.size(); col++) {
        int d1 = row + col, d2 = row - col;
        if (cols.count(col) || diag1.count(d1) || diag2.count(d2)) continue;
        cols.insert(col); diag1.insert(d1); diag2.insert(d2);
        board[row][col] = 'Q';
        dfs(row + 1, board, cols, diag1, diag2, res);
        board[row][col] = '.'; // 回溯
        cols.erase(col); diag1.erase(d1); diag2.erase(d2);
    }
}

题目3：岛屿数量（LeetCode 200）

题目描述：统计二维网格中岛屿的数量（1为陆地，0为水）。

思路：

• 遍历每个陆地单元格，使用DFS标记整个岛屿。
• 每次DFS后岛屿数量加1。

代码：

int numIslands(vector<vector<char>>& grid) {
    int res = 0;
    int m = grid.size(), n = grid[0].size();
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1' && !visited[i][j]) {
                dfs(grid, i, j, visited);
                res++;
            }
        }
    }
    return res;
}

void dfs(vector<vector<char>>& grid, int x, int y, vector<vector<bool>>& visited) {
    if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || 
        visited[x][y] || grid[x][y] == '0') return;
    visited[x][y] = true;
    dfs(grid, x+1, y, visited);
    dfs(grid, x-1, y, visited);
    dfs(grid, x, y+1, visited);
    dfs(grid, x, y-1, visited);
}

四、DFS优化技巧

1. 剪枝：提前排除不可能的路径（如N皇后的对角线冲突检查）。
2. 记忆化搜索：避免重复计算（如动态规划中的备忘录）。
3. 迭代实现：用栈模拟递归，避免栈溢出（适合深递归场景）。

五、总结

• 适用场景：需要遍历所有可能路径或状态的问题。
• 模板步骤：
  1. 确定递归参数（当前状态、路径、结果集等）。
  2. 定义终止条件（如路径完成、到达终点）。
  3. 遍历所有可能的选择，递归探索。
  4. 回溯：恢复状态以便其他路径使用。

通过以上题目练习，您可以逐步掌握DFS的核心思想和实战技巧。建议从简单问题开始，逐步挑战复杂场景！

深度优先搜索（DFS）是一种强大的算法思想，在解决许多类型的问题时都非常有效。以下为你介绍不同类型的经典 OJ 题目，适合使用 C++ 深度优先搜索来解决：

1. 排列组合问题

• 全排列问题（LeetCode 46）
  • 题目描述：给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。
  • 解题思路：使用 DFS 对每个位置进行尝试填充不同的数字，同时使用一个标记数组记录数字是否已经被使用过，避免重复使用。当所有位置都填充完毕时，得到一个全排列。
• 组合总和（LeetCode 39）
  • 题目描述：给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。
  • 解题思路：通过 DFS 递归地尝试选择不同的数字加入组合，同时更新目标值，若目标值为 0 则得到一个有效组合；若目标值小于 0 则回溯。

2. 图论相关问题

• 岛屿数量（LeetCode 200）
  • 题目描述：给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
  • 解题思路：遍历二维网格，当遇到陆地（'1'）时，使用 DFS 标记该岛屿的所有陆地（将其置为 '0'），每进行一次 DFS 就意味着发现一个新的岛屿。
• 太平洋大西洋水流问题（LeetCode 417）
  • 题目描述：给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。
  • 解题思路：分别从太平洋和大西洋的边界开始进行 DFS，标记能够到达太平洋和大西洋的单元格，最后找出同时能到达两个大洋的单元格。

3. 棋盘搜索问题

• 单词搜索（LeetCode 79）
  • 题目描述：给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
  • 解题思路：遍历棋盘，找到单词的起始字母后，使用 DFS 从该位置开始向四个方向搜索，同时标记已访问的单元格，确保不重复使用。
• N 皇后问题（LeetCode 51）
  • 题目描述：按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。给定一个整数 n ，返回所有不同的 n 皇后问题的解决方案。每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
  • 解题思路：逐行放置皇后，使用 DFS 递归地尝试每一列的位置，同时检查该位置是否会与之前放置的皇后产生冲突（即是否在同一列或同一斜线上），若不冲突则继续放置下一行的皇后。

4. 树相关问题

• 路径总和 II（LeetCode 113）
  • 题目描述：给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。
  • 解题思路：从根节点开始进行 DFS 遍历，记录当前路径和路径上节点值的总和，当到达叶子节点且路径总和等于目标和时，将该路径加入结果集。
• 二叉树的所有路径（LeetCode 257）
  • 题目描述：给定一个二叉树，返回所有从根节点到叶子节点的路径。
  • 解题思路：使用 DFS 遍历二叉树，在遍历过程中记录路径，当到达叶子节点时，将该路径加入结果集。

深度优先搜索（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法，在C++ 中常被用于解决各类问题。下面从原理、实现方式和经典OJ题示例来介绍：

一、基本原理

可以把它想象成在一个迷宫中探险，从入口进入后，遇到岔路时，先选择其中一条路一直走下去，直到走到死胡同（无法继续前进）或者达到目标，此时再退回到上一个岔路口，选择另一条没走过的路继续探索，直到遍历完整个迷宫或找到目标。

在数据结构的图或树中，DFS从起始节点开始，沿着一条路径尽可能深地探索，访问完一个节点后，就递归地去访问该节点的未访问过的邻接节点。若一个节点的所有邻接节点都已被访问，就回溯到该节点的父节点，继续探索其他未访问路径。

二、C++实现方式

通常有递归和非递归（利用栈）两种实现方式：

• 递归实现：代码简洁直观，符合DFS的思路。以下是一个简单的图的DFS递归实现示例：

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

const int N = 1000;  // 假设图中节点的最大数量
vector<int> graph[N];  // 邻接表存储图
bool visited[N];  // 记录节点是否被访问过

// DFS递归函数
void dfs(int node) {
    visited[node] = true;  // 标记当前节点已访问
    cout << node << " ";  // 这里简单处理，输出当前访问的节点
    for (int neighbor : graph[node]) {  // 遍历当前节点的所有邻接节点
        if (!visited[neighbor]) {  // 如果邻接节点未被访问
            dfs(neighbor);  // 递归访问邻接节点
        }
    }
}

使用时，先构建图的邻接关系，例如：

int main() {
    // 添加边构建图，这里简单示例
    graph[1].push_back(2);
    graph[2].push_back(1);
    graph[1].push_back(3);
    graph[3].push_back(1);

    // 初始化访问数组
    for (int i = 0; i < N; ++i) {
        visited[i] = false;
    }

    // 从节点1开始进行深度优先搜索
    dfs(1); 

    return 0;
}

• 非递归实现：使用栈来模拟递归调用的过程。以下是对应的非递归实现示例：

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

const int N = 1000;  
vector<int> graph[N];  
bool visited[N];  

void dfs_non_recursive(int start) {
    stack<int> stk;
    stk.push(start);
    visited[start] = true;

    while (!stk.empty()) {
        int node = stk.top();
        stk.pop();
        cout << node << " ";

        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                stk.push(neighbor);
                visited[neighbor] = true;
            }
        }
    }
}

使用方式和递归实现类似，先构建图和初始化访问数组，再调用dfs_non_recursive函数开始搜索。

三、OJ经典题示例

1. 全排列问题

题目描述：输出自然数1到n所有不重复的排列，即n的全排列，要求所产生的任一数字序列中不允许出现重复的数字。 解题思路：用一个数组path存储当前排列，一个布尔数组book标记数字是否已使用。从第一个位置开始，依次尝试将未使用的数字放入当前位置，然后递归处理下一个位置，当处理到第n + 1个位置时，说明得到一个全排列，输出结果。 示例代码：

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

const int N = 15;
int n;
int path[N];  // 存储数字的数组
bool book[N];  // 标记数组，标记数字是否已使用

// u为当前处理的位置
void dfs(int u) {
    // 递归出口，当处理到n + 1个位置，说明得到一个全排列
    if (u == n + 1) { 
        for (int i = 1; i <= n; i++)
            printf("%3d", path[i]);
        cout << endl;
        return;
    }

    // 枚举手里面所有的数字
    for (int i = 1; i <= n; i++) { 
        // 数字不能被标记过，即未使用过
        if (!book[i]) { 
            book[i] = true;  // 标记数字i已使用
            path[u] = i;  // 将数字i放到当前位置u
            dfs(u + 1);  // 递归处理下一个位置
            book[i] = false;  // 回溯，取消数字i的标记
        }
    }
}

int main() {
    cin >> n;
    dfs(1);  // 从第一个位置开始填充
    return 0;
}

2. 组合的输出

题目描述：从n个元素中抽出r个元素（不分顺序且r≤n），用递归的方法输出所有组合。例如n = 5，r = 3，输出所有的组合情况 。 解题思路：同样使用递归，用一个数组存储当前组合，每次从上次选择的元素的下一个位置开始选择，保证组合中的元素递增且不重复。当选择的元素个数达到r时，输出该组合。 示例代码：

#include <iostream>
using namespace std;

const int N = 20;
int n, r;
int combination[N];  // 存储组合的数组

// u为当前处理的位置，last为上一个选择的元素
void dfs(int u, int last) {
    if (u == r) {  // 当选择的元素个数达到r
        for (int i = 0; i < r; i++)
            cout << combination[i] << " ";
        cout << endl;
        return;
    }

    for (int i = last + 1; i <= n; i++) {  // 从last + 1开始选择
        combination[u] = i;
        dfs(u + 1, i);  // 递归选择下一个元素
    }
}

int main() {
    cin >> n >> r;
    dfs(0, 0);
    return 0;
}