引言

深度优先搜索（DFS）是一种在树或图中进行遍历的算法，它通过沿着一条路径深入探索，直到这条路径的终点，然后回溯并探索其他路径。DFS在算法设计中应用广泛，尤其在解决路径发现、拓扑排序、谜题解决、连通性检测和迷宫生成等问题中表现出色。本文将深入解析DFS的核心例题，并提供实战技巧。

一、DFS基础概念

深度优先搜索（DFS）的核心思想是尽可能深地搜索树的分支，直到达到叶子节点，然后回溯到前一个节点，继续搜索其他分支。

1.1 递归实现

递归实现DFS是最直观的方式，通过递归调用自身来探索所有可能的路径。

void dfsRecursive(TreeNode* node) {
    if (node == nullptr) return;
    // 处理当前节点
    dfsRecursive(node->left);  // 探索左子树
    dfsRecursive(node->right); // 探索右子树
}

1.2 迭代实现

迭代实现DFS通常使用栈来模拟递归的过程。

void dfsIterative(TreeNode* root) {
    stack<TreeNode*> stk;
    stk.push(root);
    while (!stk.empty()) {
        TreeNode* node = stk.top();
        stk.pop();
        // 处理当前节点
        if (node->right) stk.push(node->right);
        if (node->left) stk.push(node->left);
    }
}

二、DFS核心例题解析

2.1 迷宫问题

给定一个二维数组，其中0表示可以走的路径，1表示障碍物，找出从起点到终点的路径。

bool dfsMaze(vector<vector<int>>& maze, vector<int>& path, int x, int y) {
    if (x < 0 || x >= maze.size() || y < 0 || y >= maze[0].size() || maze[x][y] == 1) return false;
    if (x == maze.size() - 1 && y == maze[0].size() - 1) {
        path.push_back({x, y});
        return true;
    }
    path.push_back({x, y});
    maze[x][y] = 1; // 标记为已访问
    if (dfsMaze(maze, path, x + 1, y) || dfsMaze(maze, path, x - 1, y) ||
        dfsMaze(maze, path, x, y + 1) || dfsMaze(maze, path, x, y - 1)) {
        return true;
    }
    path.pop_back();
    maze[x][y] = 0; // 回溯
    return false;
}

2.2 岛屿问题

给定一个二维数组，其中0表示水，1表示陆地，计算岛屿的数量。

int dfsIslands(vector<vector<int>>& grid, int i, int j) {
    if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == 0) return 0;
    grid[i][j] = 0; // 标记为已访问
    return 1 + dfsIslands(grid, i + 1, j) + dfsIslands(grid, i - 1, j) +
           dfsIslands(grid, i, j + 1) + dfsIslands(grid, i, j - 1);
}

2.3 朋友圈问题

给定一个用户关系列表，其中每个元素是一个用户，用户之间的关系以列表的形式给出，找出所有好友圈。

vector<vector<int>> dfsFriendCircles(vector<vector<int>>& M) {
    vector<vector<int>> result;
    vector<bool> visited(M.size(), false);
    for (int i = 0; i < M.size(); ++i) {
        if (!visited[i]) {
            vector<int> circle;
            dfs(M, visited, circle, i);
            result.push_back(circle);
        }
    }
    return result;
}

void dfs(vector<vector<int>>& M, vector<bool>& visited, vector<int>& circle, int i) {
    visited[i] = true;
    for (int j = 0; j < M[i].size(); ++j) {
        if (M[i][j] == 1 && !visited[j]) {
            circle.push_back(j);
            dfs(M, visited, circle, j);
        }
    }
}

三、实战技巧

3.1 空间优化

在DFS中，递归可能会导致大量的函数调用栈，导致空间复杂度过高。可以通过迭代实现或使用尾递归优化来减少空间复杂度。

3.2 时间优化

对于包含大量重复子问题的DFS问题，可以使用记忆化搜索来避免重复计算，提高算法效率。

3.3 注意边界条件

在实现DFS时，要特别注意边界条件，如数组越界、空指针等，以避免程序出错。

3.4 逻辑清晰

在编写DFS代码时，要确保逻辑清晰，便于理解和维护。

总结

深度优先搜索（DFS）是一种强大的算法，在解决树和图相关问题时具有广泛的应用。通过深入理解DFS的基础概念、核心例题和实战技巧，我们可以更好地运用DFS解决实际问题。