← 上一课第 13 课 / 40下一课 →

🔦 DFS — 深入到底的探索精神

DFS是递归的天然表达，岛屿计数、连通分量、周长计算的核心

📖 DFS的核心概念

深度优先搜索（DFS, Depth-First Search）从起点出发，沿一条路径尽可能深入，直到无法继续再回溯。DFS 用递归或栈实现，适合解决连通性问题、路径搜索、拓扑排序等。DFS 不保证最短路径，但在空间效率和实现简洁性上往往优于 BFS。

DFS的两种实现: 递归DFS (最常用): def dfs(node): if base_case: return process(node) for neighbor in neighbors: dfs(neighbor) 迭代DFS (用栈): def dfs(start): stack = [start] while stack: node = stack.pop() process(node) for neighbor in neighbors: stack.append(neighbor) DFS vs BFS 选择指南: ┌──────────────────┬──────────┬──────────┐ │ 问题 │ 选DFS │ 选BFS │ ├──────────────────┼──────────┼──────────┤ │ 最短路径(无权) │ ✗ │ ✓ │ │ 连通分量 │ ✓ │ ✓ │ │ 拓扑排序 │ ✓ │ ✓(Kahn) │ │ 所有路径枚举 │ ✓ │ ✗ │ │ 回溯/排列组合 │ ✓ │ ✗ │ │ 检测环 │ ✓ │ ✗ │ │ 空间效率 │ O(h) │ O(w) │ └──────────────────┴──────────┴──────────┘

1. DFS 在网格中的方向数组

# 四方向（上下左右）
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

# 八方向（含对角线）
directions = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]

# 边界检查
def in_bounds(r, c, rows, cols):
    return 0 <= r < rows and 0 <= c < cols

2. 网格 DFS 通用模板

def dfs(grid, r, c, visited):
    rows, cols = len(grid), len(grid[0])
    # 边界检查 + 已访问检查
    if not (0 <= r < rows and 0 <= c < cols):
        return
    if (r, c) in visited or grid[r][c] == '0':
        return
    
    visited.add((r, c))  # 或 grid[r][c] = '0' (原地修改)
    
    # 四方向递归
    for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
        dfs(grid, r+dr, c+dc, visited)

🎯 题目一：岛屿数量 (LC 200)

题目描述：给你一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算网格中岛屿的数量。

示例: 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 DFS淹没过程: 扫描(0,0)='1' → count=1 DFS: (0,0)→(0,1)→(1,1)→(1,0) 全部标为'0' 继续扫描(2,2)='1' → count=2 DFS: (2,2) 标为'0' 继续扫描(3,3)='1' → count=3 DFS: (3,3)→(3,4) 全部标为'0' 结果: 3

思路分析

DFS 淹没：
1. 遍历网格，遇到 '1' → count++
2. DFS 将所有相连的 '1' 改为 '0'（淹没岛屿）
3. 继续扫描
DFS 比 BFS 更简洁，原地修改不需要额外 visited 集合。
时间复杂度：O(m×n)，空间复杂度：O(m×n)（递归栈最坏）

代码实现

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        rows, cols = len(grid), len(grid[0])
        count = 0
        
        def dfs(r, c):
            if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != '1':
                return
            grid[r][c] = '0'
            for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
                dfs(r + dr, c + dc)
        
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    count += 1
                    dfs(r, c)
        return count

复杂度分析

时间复杂度：O(m×n)

空间复杂度：O(m×n) — 递归栈

变体练习

🎯 题目二：岛屿的最大面积 (LC 695)

题目描述：给定一个包含 0 和 1 的二维数组，找到最大的岛屿面积。岛屿是 1 的连通区域。

示例: 0 1 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 1 1 岛屿1面积: 1+1+1 = 3 (左上) 岛屿2面积: 1+1+1+1+1 = 5 (右下) 最大面积 = 5 DFS返回面积: area(r,c) = 1 + area(r+1,c) + area(r-1,c) + area(r,c+1) + area(r,c-1)

思路分析

DFS 返回面积：
与岛屿数量类似，但 DFS 函数返回当前岛屿的面积。
area(r, c) = 1 + 上下左右四个方向的 DFS 面积之和。
遍历所有格子，取最大面积。
时间复杂度：O(m×n)，空间复杂度：O(m×n)

代码实现

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        
        def dfs(r, c):
            if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != 1:
                return 0
            grid[r][c] = 0
            return 1 + dfs(r+1,c) + dfs(r-1,c) + dfs(r,c+1) + dfs(r,c-1)
        
        max_area = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    max_area = max(max_area, dfs(r, c))
        return max_area

复杂度分析

时间复杂度：O(m×n)

空间复杂度：O(m×n)

DFS 返回值的技巧非常通用：岛屿面积返回 int，连通分量信息返回任何需要的类型。关键是 DFS 函数的返回值代表"以当前节点为起点的子问题答案"。

变体练习

🎯 题目三：岛屿的周长 (LC 463)

题目描述：给定一个二维网格，1 表示陆地，0 表示水域。网格中的格子水平和垂直相连。计算岛屿的周长。

示例: 0 1 0 0 1 1 0 0 0 0 0 1 周长计算方法: 每个'1'贡献4条边 每对相邻的'1'减少2条边(共享的边不算周长) 方法1: DFS数边 遍历每个'1', 检查4个方向: - 出界或为'0' → 贡献1条边 方法2: 公式法 周长 = 4×陆地数 - 2×相邻边数 上图: 陆地=4, 相邻边=2(上1+右1) 周长 = 4×4 - 2×2 = 12

思路分析

方法一：DFS 数边：
遍历每个 '1'，检查四个方向，如果出界或为 '0'，则贡献一条边。
时间复杂度：O(m×n)
方法二：公式法：
周长 = 4 × 陆地数量 - 2 × 水平相邻对数 - 2 × 垂直相邻对数
时间复杂度：O(m×n)，实现更简洁

代码实现（方法一）

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        perimeter = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
                        nr, nc = r + dr, c + dc
                        if not (0 <= nr < rows and 0 <= nc < cols) or grid[nr][nc] == 0:
                            perimeter += 1
        return perimeter

复杂度分析

时间复杂度：O(m×n)

空间复杂度：O(1)

变体练习

成就解锁：DFS深潜者 — 掌握网格DFS淹没、面积计算、周长统计三大技巧
LeetCode AC验证：LC 200 Number of Islands ✅ | LC 695 Max Area of Island ✅ | LC 463 Island Perimeter ✅

📝 课后练习

  1. LC 130 被围绕的区域（边界DFS）
  2. LC 417 太平洋大西洋水流问题（反向DFS）
  3. LC 827 最大人工岛（Hard）
  4. LC 733 图像渲染（简单DFS练习）
  5. LC 1020 飞地的数量

🔑 本课要点回顾

📚 扩展阅读

思考题：如果网格非常大（如 10000×10000），DFS 的递归深度可能导致栈溢出。如何避免？提示：使用迭代版 DFS（显式栈）或 BFS 代替。

🔬 并查集 — 连通性的另一种解法

并查集（Union-Find）是解决连通性问题的另一种利器，与DFS/BFS殊途同归，但在某些场景下更高效，特别是需要动态合并集合时。

并查集的原理: 初始: 每个元素各自为一个集合 {0} {1} {2} {3} {4} {5} union(0,1): {0,1} {2} {3} {4} {5} union(2,3): {0,1} {2,3} {4} {5} union(1,3): {0,1,2,3} {4} {5} union(4,5): {0,1,2,3} {4,5} find(0) = find(3) → 同一集合 → 连通! find(0) ≠ find(4) → 不连通! 优化: 1. 路径压缩: find时把节点直接挂到根 2. 按秩合并: 小树挂大树 → 均摊 O(α(n)) ≈ O(1)

并查集模板

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n  # 连通分量数
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        # 按秩合并
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        self.count -= 1
        return True
并查集 vs DFS/BFS：DFS/BFS 适合静态图一次性查询，并查集适合动态合并（如不断添加边）和多次查询。LC 200 岛屿数量用并查集也能解。
思考题：LC 200 岛屿数量如果用并查集实现，该怎么处理？提示：遍历网格，遇到 '1' 就与上方和左方的 '1' 合并，最终连通分量数即为岛屿数。注意水域不需要初始化为独立集合。