449_BFS与DFS面试题¶

一句话说明¶

BFS（广度优先）用队列按层探索，适合找最短路径；DFS（深度优先）用递归/栈一路到底，适合找所有路径/连通分量，两者是图和树题的核心算法。

核心知识点¶

白话理解¶

BFS 像水波扩散——从起点一圈一圈往外扩，最先到达终点时走的路就是最短路。DFS 像走迷宫——碰壁就退回来换方向，直到走出迷宫或确认无路可走。

对比¶

特性	BFS	DFS
数据结构	队列	栈（递归）
适合问题	最短路径、最少步数	所有路径、连通性、拓扑
空间复杂度	O(宽度)	O(深度)
是否保证最短	是（无权图）	否

经典题目与解法¶

题目1：岛屿数量（LeetCode 200，DFS 连通分量）¶

题意：给出 0/1 网格，1 是陆地，0 是水，找连通的陆地岛屿数量。

def num_islands(grid):
    """
    DFS：遇到陆地就 DFS 把整个岛屿变成 0（标记已访问），岛屿数+1
    """
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        """从 (r,c) 开始 DFS，把连通的陆地全变成 0"""
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return                         # 越界
        if grid[r][c] != '1':
            return                         # 水域或已访问

        grid[r][c] = '0'                   # 标记为已访问（原地修改）
        dfs(r + 1, c)                      # 向下
        dfs(r - 1, c)                      # 向上
        dfs(r, c + 1)                      # 向右
        dfs(r, c - 1)                      # 向左

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':          # 发现新陆地（新岛屿）
                count += 1
                dfs(r, c)                  # DFS 标记整个岛屿

    return count

# 测试
grid1 = [
    ["1","1","1","1","0"],
    ["1","1","0","1","0"],
    ["1","1","0","0","0"],
    ["0","0","0","0","0"]
]
print(num_islands(grid1))  # 1

grid2 = [
    ["1","1","0","0","0"],
    ["1","1","0","0","0"],
    ["0","0","1","0","0"],
    ["0","0","0","1","1"]
]
print(num_islands(grid2))  # 3

时间复杂度：O(m×n) 每个格子最多访问一次
空间复杂度：O(m×n) 递归栈

题目2：二叉树的最小深度（LeetCode 111，BFS 最短路）¶

题意：找从根节点到最近叶子节点的最短路径（层数）。

from collections import deque

def min_depth(root):
    """
    BFS：按层探索，第一次遇到叶子节点时就是最短深度
    DFS 也能做，但 BFS 更直观
    """
    if not root:
        return 0

    queue = deque([(root, 1)])             # (节点, 当前深度)

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

        # 叶子节点：没有左右子树
        if not node.left and not node.right:
            return depth                   # BFS 第一次到叶子就是最短路

        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))

    return 0

时间复杂度：O(n) 最坏遍历所有节点
空间复杂度：O(w) w 是最大宽度

题目3：单词接龙（LeetCode 127，BFS 最短路经典）¶

题意：给定词表和起始词、结束词，每次改变一个字母（且改后必须在词表中），找从起始词到结束词的最短变换步数。

from collections import deque

def ladder_length(begin_word, end_word, word_list):
    """
    BFS：把每个词当成图节点，相差一个字母的词之间有边
    找 begin_word 到 end_word 的最短路径
    """
    word_set = set(word_list)              # 转成集合，O(1)查询
    if end_word not in word_set:
        return 0                           # 目标词不在词表，无解

    queue = deque([(begin_word, 1)])       # (当前词, 步数)
    visited = {begin_word}                 # 已访问的词，避免重复

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

        for i in range(len(word)):         # 枚举每个位置
            for c in 'abcdefghijklmnopqrstuvwxyz':  # 尝试每个字母
                new_word = word[:i] + c + word[i+1:]  # 替换一个字母

                if new_word == end_word:
                    return steps + 1       # 找到终点

                if new_word in word_set and new_word not in visited:
                    visited.add(new_word)
                    queue.append((new_word, steps + 1))

    return 0                               # 无法到达

# 测试
word_list = ["hot","dot","dog","lot","log","cog"]
print(ladder_length("hit", "cog", word_list))  # 5（hit→hot→dot→dog→cog）
print(ladder_length("hit", "cog", ["hot","dot","dog","lot","log"]))  # 0

时间复杂度：O(N × L × 26) N是词表大小，L是词长
空间复杂度：O(N × L)

题目4：全排列（LeetCode 46，DFS 回溯）¶

def permute(nums):
    """
    DFS + 回溯：每次从剩余元素中选一个加入路径，选完后撤销选择
    """
    result = []
    path = []                              # 当前路径

    def backtrack(remaining):
        if not remaining:                  # 路径长度等于nums，找到一个排列
            result.append(path[:])         # 注意拷贝，path是引用
            return

        for i in range(len(remaining)):
            path.append(remaining[i])      # 选择当前元素
            backtrack(remaining[:i] + remaining[i+1:])  # 递归，剩余元素去掉已选的
            path.pop()                     # 撤销选择（回溯）

    backtrack(nums)
    return result

print(permute([1, 2, 3]))  # [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

面试技巧¶

最短路径用 BFS：无权图中 BFS 一定找到最短路，DFS 不能保证
回溯三要素：选择、递归、撤销——每次做选择后必须撤销，保证状态干净
visited 集合防重复访问：BFS/DFS 都需要，否则会无限循环
DFS 适合"找所有方案"：全排列、子集、组合都是 DFS + 回溯
岛屿题说清楚去重策略：原地修改（grid[r][c] = '0'）vs. 单独维护 visited

速查表¶

# BFS 模板
from collections import deque
def bfs(start, end, graph):
    queue = deque([start])
    visited = {start}
    steps = 0
    while queue:
        steps += 1
        for _ in range(len(queue)):       # 按层处理
            node = queue.popleft()
            for neighbor in graph[node]:
                if neighbor == end:
                    return steps
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
    return -1  # 不可达

# DFS 模板（回溯）
def dfs(path, remaining, result):
    if is_complete(path):
        result.append(path[:])            # 注意拷贝
        return
    for choice in remaining:
        path.append(choice)               # 做选择
        dfs(path, remaining - {choice}, result)
        path.pop()                        # 撤销选择

# 图 DFS 模板
def dfs_graph(node, visited, graph):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_graph(neighbor, visited, graph)

场景	算法	关键点
最短步数	BFS	visited集合防重
连通分量	DFS/BFS	标记访问
全排列/组合	DFS回溯	选择+撤销
岛屿数量	DFS原地标记	改grid为0
单词接龙	BFS	26字母枚举