面试官最爱问的图遍历：BFS在LeetCode「岛屿数量」和「打开转盘锁」中的实战拆解

面试官最爱问的图遍历：BFS在LeetCode「岛屿数量」和「打开转盘锁」中的实战拆解

最近在技术面试中，图的广度优先搜索（BFS）算法成为了高频考点。不同于教科书式的理论讲解，本文将聚焦LeetCode上两道经典题目——200.岛屿数量和752.打开转盘锁，带你深入理解BFS在实际问题中的应用技巧。

1. BFS算法核心思想与面试价值

BFS之所以成为面试官的最爱，是因为它能考察候选人对以下关键点的掌握程度：

• 层次遍历思维：像剥洋葱一样逐层解决问题
• 队列的灵活运用：先进先出的数据结构特性
• 状态空间搜索：将问题转化为图遍历的能力
• 时间复杂度把控：对算法效率的敏感度

在面试中，单纯背诵BFS模板远远不够。面试官更看重你如何将抽象算法落地到具体问题场景。下面我们通过两道经典题目，看看BFS如何大显身手。

2. LeetCode 200：岛屿数量问题实战

2.1 问题建模技巧

岛屿数量问题要求计算二维网格中岛屿的个数（'1'代表陆地，'0'代表水）。关键在于如何将网格转化为图结构：

grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ]

建模思路：

• 每个网格单元格视为图中的一个节点
• 相邻的陆地单元格（上下左右）形成边连接
• 岛屿就是连通分量，问题转化为求连通分量数量

2.2 BFS实现细节与优化

标准BFS解法需要特别注意以下实现细节：

from collections import deque def numIslands(grid): if not grid: return 0 rows, cols = len(grid), len(grid[0]) visited = set() island_count = 0 def bfs(r, c): queue = deque() visited.add((r, c)) queue.append((r, c)) while queue: row, col = queue.popleft() directions = [[1,0], [-1,0], [0,1], [0,-1]] for dr, dc in directions: r, c = row + dr, col + dc if (r in range(rows) and c in range(cols) and grid[r][c] == "1" and (r, c) not in visited): queue.append((r, c)) visited.add((r, c)) for r in range(rows): for c in range(cols): if grid[r][c] == "1" and (r, c) not in visited: bfs(r, c) island_count += 1 return island_count

关键优化点：

1. 访问标记时机：入队时立即标记，避免重复访问
2. 方向数组使用：统一处理四个方向移动
3. 边界检查：防止数组越界访问

面试陷阱：很多候选人会在出队时才标记访问，这会导致同一节点被多次加入队列，严重影响性能。

2.3 复杂度分析与变种问题

时间复杂度：O(M×N)，每个单元格最多被访问一次
空间复杂度：O(min(M,N))，队列在最坏情况下存储对角线上的节点

常见变种：

• 统计岛屿的最大面积
• 计算岛屿的周长
• 封闭岛屿数量（四周被水包围）

3. LeetCode 752：打开转盘锁的BFS解法

3.1 状态空间建模

转盘锁问题要求从"0000"开始，找到打开目标锁的最少转动次数，避开死锁组合。这实际上是一个状态空间搜索问题：

• 节点：每个锁的状态（如"0123"）
• 边：一次转动可以到达的相邻状态
• 目标：找到到目标状态的最短路径

deadends = ["0201","0101","0102","1212","2002"] target = "0202"

3.2 BFS实现中的特殊处理

from collections import deque def openLock(deadends, target): dead = set(deadends) visited = set() queue = deque([('0000', 0)]) if '0000' in dead: return -1 while queue: current, steps = queue.popleft() if current == target: return steps for i in range(4): for delta in (-1, 1): new_digit = (int(current[i]) + delta) % 10 new_state = current[:i] + str(new_digit) + current[i+1:] if new_state not in visited and new_state not in dead: visited.add(new_state) queue.append((new_state, steps + 1)) return -1

关键技巧：

1. 死锁预处理：将deadends转换为集合快速查找
2. 数字滚动处理：使用模运算处理'9'→'0'和'0'→'9'的边界情况
3. 步骤计数：将步数与状态一起存储

3.3 双向BFS优化

当目标状态明确时，双向BFS可以大幅提升效率：

def openLock(deadends, target): dead = set(deadends) if '0000' in dead or target in dead: return -1 front, back = {'0000'}, {target} visited = set() steps = 0 while front and back: if len(front) > len(back): front, back = back, front next_front = set() for current in front: if current in back: return steps if current in dead: continue visited.add(current) for i in range(4): for delta in (-1, 1): new_digit = (int(current[i]) + delta) % 10 new_state = current[:i] + str(new_digit) + current[i+1:] if new_state not in visited: next_front.add(new_state) front = next_front steps += 1 return -1

性能对比：

4. BFS在面试中的常见考察点

4.1 高频问题分类

1. 网格类问题：

   • 迷宫最短路径
   • 腐烂的橘子
   • 被围绕的区域

2. 状态转换问题：

   • 单词接龙
   • 最小基因变化
   • 滑动谜题

3. 树/图遍历：

   • 二叉树层序遍历
   • 克隆图
   • 课程表拓扑排序

4.2 面试评分要点

根据多位面试官的反馈，BFS问题的评分通常关注：

• 问题转化能力（40%）：能否将实际问题抽象为图遍历
• 实现细节处理（30%）：队列操作、访问标记等细节处理
• 复杂度分析（20%）：正确评估算法效率
• 代码整洁度（10%）：变量命名、函数拆分等

4.3 避坑指南

在最近半年的大厂面试中，候选人常犯的错误包括：

1. 忘记处理初始状态就是目标状态的情况
2. 在转盘锁问题中未正确处理数字循环
3. 网格问题中错误地使用深度优先导致非最短路径
4. 未及时标记访问状态导致重复计算

5. BFS与DFS的选择策略

虽然很多图问题既可以用BFS也可以用DFS解决，但在面试中选择合适的算法至关重要：

选择BFS当：

• 需要最短路径或最少步骤
• 问题有明显的层次结构
• 状态空间可能很大但解在浅层

选择DFS当：

• 需要遍历所有可能路径
• 问题需要回溯尝试
• 内存受限（BFS队列可能很大）

性能对比表：

在实际面试中，当面试官问"为什么选择BFS"时，能够清晰阐述上述区别会大大加分。