DFS解题模板（递归版）

python
展开代码
def dfs(参数):
    # 终止条件（越界、已访问、不符合条件）
    if 终止条件:
        return
    
    # 处理当前节点（标记已访问、记录路径等）
    处理当前节点
    
    # 递归访问相邻节点（四个方向、子节点等）
    for 方向 in 所有可能的方向:
        dfs(新参数)  # 递归
    
    # 回溯（如果需要恢复状态，如全排列问题）
    # 例如：撤销访问标记、弹出当前节点等

---

题目实战：LeetCode 200. 岛屿数量

题目描述：
给你一个由 '1'（陆地）和 '0'（水）组成的二维网格，请你计算网格中岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接形成。

示例：
输入：

展开代码
[
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

输出：3

---

DFS解题步骤

1. 确定递归函数的作用

• 目标：找到所有相邻的陆地，并将其标记为已访问，避免重复计数。
• 参数：当前网格坐标 (i, j)。

2. 终止条件

• 越界（超出网格范围）
• 当前节点是水（'0'）或已访问过

3. 处理当前节点

• 将当前陆地标记为已访问（例如，将 '1' 改为 '0'）

4. 递归访问四个方向

• 对上下左右四个方向进行递归搜索

5. 无需回溯

• 本题不需要恢复网格状态（直接修改原数组即可）

---

代码实现

python
展开代码
def numIslands(grid):
    if not grid:
        return 0
    
    count = 0
    rows, cols = len(grid), len(grid[0])
    
    def dfs(i, j):
        # 终止条件：越界或当前是水
        if i < 0 or i >= rows or j < 0 or j >= cols or grid[i][j] == '0':
            return
        
        # 处理当前节点：标记为已访问（淹没陆地）
        grid[i][j] = '0'
        
        # 递归访问四个方向
        dfs(i-1, j)  # 上
        dfs(i+1, j)  # 下
        dfs(i, j-1)  # 左
        dfs(i, j+1)  # 右
    
    # 遍历整个网格
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':
                dfs(i, j)
                count += 1  # 每次DFS后岛屿数量+1
    
    return count

---

关键点解析

1. 如何避免重复访问：
   通过将访问过的陆地 '1' 修改为 '0'，确保每个岛屿只被计数一次。

2. DFS的方向选择：
   本题需要检查上下左右四个方向，递归时会自动处理所有连通区域。

3. 时间复杂度：
   O(M×N)，每个网格点最多被访问一次。

---

DFS常见题型及变种

1. 连通性问题（如岛屿数量、朋友圈）
2. 路径问题（如二叉树路径总和、矩阵中的路径）
3. 排列组合（如全排列、子集）
4. 图的遍历（如有向图环检测）

---

面试技巧

• 先画图解释思路：画出网格和DFS的递归路径，展示你的思考过程。
• 边界条件检查：始终优先处理越界和终止条件。
• 讨论空间优化：例如本题直接修改原数组，无需额外空间；若不允许修改输入，可以用visited矩阵。

掌握这个模板后，你可以快速解决大多数DFS问题！核心是明确递归函数的职责，处理好终止条件和状态标记。