深度优先搜索（DFS）代码模板

递归实现（常用）

void dfs(int current, vector<bool>& visited, vector<vector<int>>& graph) {
    visited[current] = true;
    for (int neighbor : graph[current]) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited, graph);
        }
    }
}
 

迭代实现（栈模拟）

void dfs(int start, vector<vector<int>>& graph) {
    vector<bool> visited(graph.size(), false);
    stack<int> stk;
    stk.push(start);
    
    while (!stk.empty()) {
        int current = stk.top();
        stk.pop();
        if (!visited[current]) {
            visited[current] = true;
            for (int neighbor : graph[current]) {
                if (!visited[neighbor]) {
                    stk.push(neighbor);
                }
            }
        }
    }
}
 

解题思路框架

问题分析阶段

判断是否满足DFS适用场景：

• 需要遍历或搜索树/图结构
• 需要记录路径或状态（如回溯问题）
• 需要穷举所有可能性（如排列组合）

明确递归终止条件：

• 到达叶子节点
• 满足特定条件
• 超出限制范围

代码实现要点

状态标记与回溯：

path.push_back(current);  // 记录路径
// ...处理逻辑...
path.pop_back();         // 移除路径
 

剪枝优化：
在递归前加入条件判断，提前终止无效分支

if (isInvalidState) return;
 

常见变种处理

矩阵中的DFS：

• 使用方向数组处理四连通/八连通

  int dirs[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
   
  

• 回溯问题：

  • 组合问题注意避免重复（通过start参数控制）
  • 排列问题需要visited数组标记使用情况

• 记忆化DFS：添加dp数组存储中间结果

  if (dp[current] != -1) return dp[current];
   
  

  典型例题参考

  二叉树路径和

  void dfs(TreeNode* node, int sum, vector<int>& path, vector<vector<int>>& res) {
      if (!node) return;
      path.push_back(node->val);
      if (!node->left && !node->right && sum == node->val) {
          res.push_back(path);
      }
      dfs(node->left, sum - node->val, path, res);
      dfs(node->right, sum - node->val, path, res);
      path.pop_back();
  }
   
  

  岛屿数量问题

  void dfs(vector<vector<char>>& grid, int i, int j) {
      if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] != '1') 
          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);
  }