深度优先搜索(DFS)

算法概述

【深度优先搜索】(Depth-First Search, DFS)是一种用于遍历或搜索树/图数据结构的算法。其特点是沿着一条路径尽可能深入地搜索，直到不能再深入为止，然后回溯到前一个节点，继续搜索其他路径。

算法设计思路

DFS的核心思想是：

1. 从起点开始，选择一个方向深入探索
2. 不断深入，直到无法继续（达到目标或碰到边界）
3. 回溯到上一个状态，选择另一个方向继续探索
4. 重复上述过程直到所有可能的路径都被探索完毕

DFS通常使用函数递归或显式栈来实现回溯机制。

代码实现与解析

递归实现(以图的遍历为例)

// 邻接表表示的图
vector<vector<int>> graph;
// 访问标记数组
vector<bool> visited;

// DFS函数定义
void dfs(int node) {
    // 标记当前节点为已访问
    visited[node] = true;
    cout << "访问节点: " << node << endl;

    // 遍历所有相邻节点
    for (int neighbor : graph[node]) {
        // 如果相邻节点未被访问，则递归访问它
        if (!visited[neighbor]) {
            dfs(neighbor);
        }
    }
}

// 图的DFS遍历，处理非连通图的情况
void dfsTraversal(int n) {
    visited.resize(n, false);
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i);
        }
    }
}

非递归实现(使用栈)

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

    while (!s.empty()) {
        int node = s.top();
        s.pop();
        cout << "访问节点: " << node << endl;

        // 注意：与递归DFS相比，迭代版本的访问顺序可能不同
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                s.push(neighbor);
            }
        }
    }
}

流程图解析

DFS过程示意(以二叉树为例):

      1        第1步: 访问节点1
     / \
    2   3      第2步: 访问节点2
   / \         第3步: 访问节点4
  4   5        第4步: 访问节点5 (节点4没有子节点)
                第5步: 返回节点2
                第6步: 访问节点3 (节点2的所有路径都已探索)

复杂度分析

• 时间复杂度：O(V + E)，其中V是节点数，E是边数
  • 在邻接表表示下，每个节点和每条边都会被访问一次
  • 在邻接矩阵表示下，时间复杂度为O(V²)
• 空间复杂度：O(V)，递归实现时，递归栈的最大深度为图的深度，最坏情况为O(V)

典型应用场景

DFS在算法竞赛中有广泛应用，常见的应用场景包括：

1. 【图的遍历】与节点的发现/访问
2. 【连通分量】的识别
3. 【拓扑排序】（通过结束时间的逆序）
4. 【路径查找】问题，特别是所有路径的枚举
5. 【迷宫问题】和网格搜索
6. 【回溯算法】的框架，如排列组合、数独解决等
7. 【图的环检测】

典型例题分析

例题1: 岛屿的数量（LeetCode 200）

问题描述：给你一个由 '1'（陆地）和 '0'（水）组成的二维网格，请你计算网格中岛屿的数量。岛屿由相邻的陆地连接而成，上、下、左、右四个方向视为相邻。

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

        int rows = grid.size();
        int cols = grid[0].size();
        int islands = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    islands++; // 发现一个新岛屿
                    dfs(grid, i, j); // 用DFS将整个岛屿标记为已访问
                }
            }
        }

        return islands;
    }

private:
    void dfs(vector<vector<char>>& grid, int row, int col) {
        int rows = grid.size();
        int cols = grid[0].size();

        // 边界检查和已访问检查
        if (row < 0 || col < 0 || row >= rows || col >= cols || grid[row][col] != '1')
            return;

        grid[row][col] = '2'; // 标记为已访问（可以设为任何非'1'值）

        // 探索上下左右四个方向
        dfs(grid, row + 1, col);
        dfs(grid, row - 1, col);
        dfs(grid, row, col + 1);
        dfs(grid, row, col - 1);
    }
};

分析：

• 时间复杂度：O(M×N)，其中M是行数，N是列数
• 空间复杂度：O(M×N)，最坏情况下，整个网格都是陆地，递归调用深度为M×N
• 核心思想：当发现一个陆地格子时，使用DFS将整个相连的陆地区域标记为已访问，避免重复计数

例题2: 全排列（LeetCode 46）

问题描述：给定一个不含重复数字的数组，返回其所有可能的全排列。

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> current;
        vector<bool> used(nums.size(), false);

        dfs(nums, used, current, result);
        return result;
    }

private:
    void dfs(vector<int>& nums, vector<bool>& used, vector<int>& current, vector<vector<int>>& result) {
        // 达到排列长度，记录结果
        if (current.size() == nums.size()) {
            result.push_back(current);
            return;
        }

        // 尝试每个数字
        for (int i = 0; i < nums.size(); i++) {
            // 跳过已使用的数字
            if (used[i]) continue;

            // 选择当前数字
            used[i] = true;
            current.push_back(nums[i]);

            // 递归生成后续排列
            dfs(nums, used, current, result);

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

分析：

• 时间复杂度：O(n!)，其中n是数组长度，全排列的数量为n!
• 空间复杂度：O(n)，递归调用栈的深度为n，额外使用了used数组和current数组
• 核心思想：使用DFS和回溯技术生成所有可能的排列

易错点与调试技巧

1. 【访问标记】忘记标记节点为已访问，导致无限递归 ```cpp // 错误写法 void dfs_wrong(int node) { // 忘记标记为已访问 for (int neighbor : graph[node]) {

    if (!visited[neighbor]) {
        dfs_wrong(neighbor);
    }
   

   } }

// 正确写法 void dfs_correct(int node) { visited[node] = true; // 立即标记为已访问 for (int neighbor : graph[node]) { if (!visited[neighbor]) { dfs_correct(neighbor); } } }

2. 【边界条件】检查不充分，特别是在网格问题中
```cpp
// 错误写法
void dfs_grid_wrong(vector<vector<int>>& grid, int row, int col) {
    // 缺少边界检查
    if (grid[row][col] != 1) return; // 可能导致数组越界

    grid[row][col] = 2;
    dfs_grid_wrong(grid, row+1, col);
    // ...其他方向
}

// 正确写法
void dfs_grid_correct(vector<vector<int>>& grid, int row, int col) {
    int rows = grid.size();
    int cols = grid[0].size();

    // 完整的边界检查
    if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] != 1)
        return;

    grid[row][col] = 2;
    dfs_grid_correct(grid, row+1, col);
    // ...其他方向
}

1. 【递归深度】过深导致栈溢出

   // 处理递归深度过大的情况
   void dfs_with_depth_check(int node, int depth) {
    if (depth > MAX_DEPTH) return; // 限制递归深度
   
    visited[node] = true;
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs_with_depth_check(neighbor, depth + 1);
        }
    }
   }
   

优化策略

1. 【记忆化搜索】避免重复计算 ```cpp // 使用记忆化数组避免重复状态计算 vector memo;

int dfs_with_memo(int state) { if (memo[state] != -1) return memo[state]; // 已计算过的状态直接返回

// 计算结果
int result = 0;
// ...计算逻辑

memo[state] = result; // 存储结果
return result;

}

2. 【剪枝】提前终止无效搜索路径
```cpp
void dfs_with_pruning(int node, int target, int current_sum) {
    if (current_sum > target) {
        return; // 剪枝：当前和已超过目标，无需继续
    }

    if (current_sum == target) {
        // 找到解
        return;
    }

    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            visited[neighbor] = true;
            dfs_with_pruning(neighbor, target, current_sum + value[neighbor]);
            visited[neighbor] = false;
        }
    }
}

练习题推荐

1. LeetCode 733: 图像渲染（简单DFS网格问题）
2. LeetCode 200: 岛屿数量（中等难度网格DFS）
3. LeetCode 695: 岛屿的最大面积（中等难度网格DFS）
4. LeetCode 46: 全排列（中等难度回溯）
5. LeetCode 79: 单词搜索（中等难度网格DFS）
6. LeetCode 417: 太平洋大西洋水流问题（中等难度多源DFS）
7. POJ 1321: 棋盘问题（经典DFS练习）
8. CodeForces 510B: Fox And Two Dots（环检测DFS）

总结

深度优先搜索是一种强大的图遍历算法，广泛应用于各类问题求解中。其核心思想是尽可能深入探索一条路径，再回溯尝试其他可能的选择。掌握DFS的关键在于：

1. 理解递归与回溯的本质
2. 正确处理访问标记和边界条件
3. 灵活运用剪枝和记忆化等优化技巧

在ACM比赛中，DFS通常与回溯、记忆化、剪枝等技术结合使用，能够高效解决图遍历、排列组合、路径查找等各类问题。