BFS解题模板（队列版）

python
from collections import deque

def bfs(起始点):
    # 初始化队列和访问标记
    queue = deque()
    queue.append(起始点)
    visited = set()
    visited.add(起始点)
    
    while queue:
        # 弹出当前节点
        node = queue.popleft()
        
        # 处理当前节点（例如记录路径、判断条件等）
        处理当前节点
        
        # 遍历相邻节点
        for neighbor in 获取相邻节点(node):
            if neighbor 未越界 and neighbor 未访问:
                queue.append(neighbor)
                visited.add(neighbor)  # 必须在此处标记已访问

题目实战：LeetCode 200. 岛屿数量（BFS版）

解题思路：
与DFS不同，BFS会逐层向外扩散搜索。每次遇到陆地 '1' 时，将其加入队列，并标记为已访问，直到队列为空，完成一个岛屿的搜索。

BFS解题步骤

1. 初始化队列和访问标记

• 用队列存储待处理的陆地坐标
• 直接修改原数组标记访问（或使用独立visited）

2. 循环处理队列

• 弹出队列中的坐标
• 检查四个方向的新坐标是否合法且为未访问的陆地

3. 扩散搜索

• 将合法的新陆地坐标加入队列并标记

代码实现

python
from collections import deque

def numIslands(grid):
    if not grid:
        return 0
    
    count = 0
    rows, cols = len(grid), len(grid[0])
    
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':
                # BFS开始
                queue = deque()
                queue.append((i, j))
                grid[i][j] = '0'  # 标记为已访问
                
                while queue:
                    x, y = queue.popleft()
                    # 四个方向扩散
                    for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
                        nx, ny = x + dx, y + dy
                        # 检查是否合法且为陆地
                        if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == '1':
                            queue.append((nx, ny))
                            grid[nx][ny] = '0'  # 入队时立即标记
                count += 1
    return count

关键点解析

1. 队列的核心作用：
   保证按层级顺序处理节点，类似“波纹扩散”效果。

2. 访问标记的时机：
   必须在入队时标记，而非出队时。若在出队时标记，会导致同一节点被重复加入队列。

3. 时间复杂度：
   O(M×N)，与DFS相同，但空间复杂度在最坏情况下（如全为陆地）为 O(min(M,N))，因为队列中最多同时存储对角线上的节点。

BFS常见题型及变种

1. 最短路径问题（如迷宫的最短步数、单词接龙）
2. 层级遍历（如二叉树的层序遍历、朋友圈层级）
3. 拓扑排序（如课程安排）
4. 扩散问题（如腐烂的橘子、病毒传播）

面试技巧

• 队列实现选择：
  Python中用deque实现高效的头尾操作，避免用列表模拟队列（pop(0)是O(n)操作）。

• 方向遍历技巧：
  用方向数组dx, dy表示四个方向，代码更简洁。

• 空间优化讨论：
  若不允许修改输入数据，需声明visited矩阵；若允许修改，直接修改原数组可节省空间。

• 解释BFS与DFS的选择：
  BFS适合找最短路径，DFS适合找连通性（本题两者均可）。若面试官追问差异，可结合时间复杂度展开。

掌握BFS模板后，可解决大多数层级扩散类问题。核心是理解队列的“先进先出”特性，以及正确处理访问标记的时机。