30 秒速览

  • DFS：深度优先，一条路走到黑，用递归/栈
  • BFS：广度优先，逐层扩展，用队列
  • DFS 适合：路径问题、连通性、所有方案
  • BFS 适合：最短路径、最少步数、层序遍历

一、直觉建立

走迷宫

DFS（深度优先）：

  • 选择一条路一直走
  • 走到死胡同就回退
  • 像一个人在迷宫里探索

BFS（广度优先）：

  • 同时尝试所有相邻的路
  • 一圈一圈向外扩展
  • 像水波纹扩散

对比

特性DFSBFS
数据结构栈（递归）队列
空间O(h)，h 是深度O(w)，w 是宽度
最短路径不保证保证（无权图）
实现复杂度简单（递归）稍复杂（队列）

二、DFS 模板

递归实现

def dfs(root):
    if not root:
        return

    # 处理当前节点
    visit(root)

    # 递归处理子节点
    for child in get_children(root):
        dfs(child)

迭代实现（栈）

def dfs_iterative(root):
    stack = [root]
    visited = set()

    while stack:
        node = stack.pop()

        if node in visited:
            continue
        visited.add(node)

        visit(node)

        for child in get_children(node):
            if child not in visited:
                stack.append(child)

三、BFS 模板

from collections import deque

def bfs(root):
    queue = deque([root])
    visited = set([root])

    while queue:
        node = queue.popleft()

        visit(node)

        for child in get_children(node):
            if child not in visited:
                visited.add(child)
                queue.append(child)

BFS 求最短路径：

from collections import deque

def shortestPath(start, end):
    queue = deque([(start, 0)])  # (node, distance)
    visited = set([start])

    while queue:
        node, dist = queue.popleft()

        if node == end:
            return dist

        for neighbor in get_neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))

    return -1  # 无法到达

四、典型例题

例题 1：LC 200. 岛屿数量

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

DFS 实现

def numIslands(grid: list[list[str]]) -> int:
    if not grid:
        return 0

    m, n = len(grid), len(grid[0])
    count = 0

    def dfs(i, j):
        if i < 0 or i >= m or j < 0 or j >= n 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(m):
        for j in range(n):
            if grid[i][j] == '1':
                count += 1
                dfs(i, j)

    return count

BFS 实现

from collections import deque

def numIslands(grid: list[list[str]]) -> int:
    if not grid:
        return 0

    m, n = len(grid), len(grid[0])
    count = 0
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                count += 1
                grid[i][j] = '0'

                queue = deque([(i, j)])
                while queue:
                    x, y = queue.popleft()
                    for dx, dy in directions:
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1':
                            grid[nx][ny] = '0'
                            queue.append((nx, ny))

    return count

复杂度：时间 O(mn)，空间 O(mn)

例题 2：LC 130. 被围绕的区域

题目：给定一个二维矩阵，包含 ‘X’ 和 ‘O’，将所有被 ‘X’ 围绕的 ‘O’ 变成 ‘X’。

思路

从边界的 ‘O’ 开始 DFS/BFS，标记所有与边界相连的 ‘O’，剩下的 ‘O’ 就是被围绕的。

def solve(board: list[list[str]]) -> None:
    if not board:
        return

    m, n = len(board), len(board[0])

    def dfs(i, j):
        if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != 'O':
            return

        board[i][j] = 'T'  # 临时标记

        dfs(i + 1, j)
        dfs(i - 1, j)
        dfs(i, j + 1)
        dfs(i, j - 1)

    # 从边界的 'O' 开始标记
    for i in range(m):
        dfs(i, 0)
        dfs(i, n - 1)
    for j in range(n):
        dfs(0, j)
        dfs(m - 1, j)

    # 遍历处理
    for i in range(m):
        for j in range(n):
            if board[i][j] == 'O':
                board[i][j] = 'X'  # 被围绕的
            elif board[i][j] == 'T':
                board[i][j] = 'O'  # 恢复边界相连的

复杂度：时间 O(mn)，空间 O(mn)

例题 3：LC 133. 克隆图

题目：给你无向连通图中的一个节点，请你返回该图的深拷贝。

DFS 实现

def cloneGraph(node: 'Node') -> 'Node':
    if not node:
        return None

    visited = {}

    def dfs(node):
        if node in visited:
            return visited[node]

        clone = Node(node.val)
        visited[node] = clone

        for neighbor in node.neighbors:
            clone.neighbors.append(dfs(neighbor))

        return clone

    return dfs(node)

BFS 实现

from collections import deque

def cloneGraph(node: 'Node') -> 'Node':
    if not node:
        return None

    visited = {node: Node(node.val)}
    queue = deque([node])

    while queue:
        curr = queue.popleft()

        for neighbor in curr.neighbors:
            if neighbor not in visited:
                visited[neighbor] = Node(neighbor.val)
                queue.append(neighbor)

            visited[curr].neighbors.append(visited[neighbor])

    return visited[node]

复杂度：时间 O(n)，空间 O(n)

例题 4：LC 1091. 二进制矩阵中的最短路径

题目：给你一个 n × n 的二进制矩阵 grid，返回从左上角到右下角的最短路径长度。

思路

BFS 天然适合求最短路径。

from collections import deque

def shortestPathBinaryMatrix(grid: list[list[int]]) -> int:
    n = len(grid)

    if grid[0][0] == 1 or grid[n-1][n-1] == 1:
        return -1

    if n == 1:
        return 1

    directions = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
    queue = deque([(0, 0, 1)])  # (row, col, distance)
    grid[0][0] = 1  # 标记为已访问

    while queue:
        r, c, dist = queue.popleft()

        for dr, dc in directions:
            nr, nc = r + dr, c + dc

            if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                if nr == n - 1 and nc == n - 1:
                    return dist + 1

                grid[nr][nc] = 1
                queue.append((nr, nc, dist + 1))

    return -1

复杂度：时间 O(n²)，空间 O(n²)

例题 5：LC 417. 太平洋大西洋水流问题

题目：给定一个矩阵，找出所有既能流向太平洋又能流向大西洋的格子坐标。

思路

反向思考：从两个海洋的边界反向 DFS/BFS，找能到达的格子。

def pacificAtlantic(heights: list[list[int]]) -> list[list[int]]:
    if not heights:
        return []

    m, n = len(heights), len(heights[0])

    pacific = set()
    atlantic = set()

    def dfs(i, j, visited, prev_height):
        if (i < 0 or i >= m or j < 0 or j >= n or
            (i, j) in visited or heights[i][j] < prev_height):
            return

        visited.add((i, j))

        dfs(i + 1, j, visited, heights[i][j])
        dfs(i - 1, j, visited, heights[i][j])
        dfs(i, j + 1, visited, heights[i][j])
        dfs(i, j - 1, visited, heights[i][j])

    # 从太平洋边界（上边和左边）开始
    for i in range(m):
        dfs(i, 0, pacific, 0)
    for j in range(n):
        dfs(0, j, pacific, 0)

    # 从大西洋边界（下边和右边）开始
    for i in range(m):
        dfs(i, n - 1, atlantic, 0)
    for j in range(n):
        dfs(m - 1, j, atlantic, 0)

    # 找两个集合的交集
    return list(pacific & atlantic)

复杂度：时间 O(mn)，空间 O(mn)

例题 6：LC 127. 单词接龙

题目：给定两个单词和一个字典，找出从 beginWord 到 endWord 的最短转换序列长度，每次只能改变一个字母。

思路

BFS 求最短路径。

from collections import deque, defaultdict

def ladderLength(beginWord: str, endWord: str, wordList: list[str]) -> int:
    if endWord not in wordList:
        return 0

    # 构建邻接表：通用状态 → 单词列表
    graph = defaultdict(list)
    for word in wordList:
        for i in range(len(word)):
            pattern = word[:i] + '*' + word[i+1:]
            graph[pattern].append(word)

    queue = deque([(beginWord, 1)])
    visited = set([beginWord])

    while queue:
        word, level = queue.popleft()

        for i in range(len(word)):
            pattern = word[:i] + '*' + word[i+1:]

            for neighbor in graph[pattern]:
                if neighbor == endWord:
                    return level + 1

                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, level + 1))

    return 0

复杂度：时间 O(M²×N)，M 是单词长度，N 是单词数

五、DFS vs BFS 选择

场景推荐
最短路径（无权）BFS
层序遍历BFS
拓扑排序BFS
所有方案/路径DFS
连通性检测都可以
判断是否存在DFS（通常更快）
空间受限（树很宽但很浅）DFS
空间受限（树很深但很窄）BFS

六、常见错误与陷阱

错误 1：忘记标记已访问

# 错误：无限循环
while queue:
    node = queue.popleft()
    for neighbor in get_neighbors(node):
        queue.append(neighbor)  # 重复加入

# 正确：标记已访问
while queue:
    node = queue.popleft()
    for neighbor in get_neighbors(node):
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append(neighbor)

错误 2：BFS 标记时机错误

# 错误：出队时才标记，可能重复入队
while queue:
    node = queue.popleft()
    visited.add(node)  # 太晚了

# 正确：入队时标记
queue.append(start)
visited.add(start)
while queue:
    ...

错误 3：DFS 栈溢出

# 对于深度很大的图，递归 DFS 可能栈溢出
# 解决：用迭代版（显式栈）

七、复盘清单

触发信号

  • 图/矩阵遍历
  • 求最短路径
  • 连通性问题
  • 所有路径/方案

实现检查

  • 已访问标记正确
  • 边界条件处理
  • 方向数组正确
  • 返回值正确

八、题目清单

DFS

题号题目难度考点
200岛屿数量Medium连通分量
130被围绕的区域Medium边界 DFS
133克隆图Medium图复制
417太平洋大西洋Medium反向 DFS
79单词搜索Medium二维 DFS

BFS

题号题目难度考点
102二叉树层序遍历Medium基本 BFS
1091二进制矩阵最短路径Medium最短路径
127单词接龙Medium最短路径
994腐烂的橘子Medium多源 BFS
310最小高度树Medium拓扑排序