LeetCode中广度优先搜索算法的示例分析

广度优先搜索（BFS）是一种常用的图遍历算法，广泛应用于解决最短路径、连通性等问题。在LeetCode中，BFS算法常用于解决树、图以及矩阵相关的题目。本文将通过几个典型的LeetCode题目，详细分析BFS算法的应用场景和实现方法。

1. 广度优先搜索算法简介

广度优先搜索是一种逐层遍历的算法，从起始节点开始，依次访问其所有邻接节点，然后再访问这些邻接节点的邻接节点，以此类推。BFS通常使用队列（Queue）来实现，确保节点按照层级顺序被访问。

BFS算法的基本步骤如下： 1. 将起始节点放入队列中。 2. 从队列中取出一个节点，访问该节点。 3. 将该节点的所有未访问过的邻接节点放入队列中。 4. 重复步骤2和3，直到队列为空。

2. LeetCode中的BFS应用示例

2.1 二叉树的层序遍历（LeetCode 102）

题目描述：给定一个二叉树，返回其节点值的层序遍历结果（即逐层从左到右访问所有节点）。

示例：

输入：
    3
   / \
  9  20
    /  \
   15   7
输出：
[
  [3],
  [9,20],
  [15,7]
]

解题思路： - 使用BFS逐层遍历二叉树。 - 在每一层遍历时，记录当前层的节点值，并将其子节点加入队列。

代码实现：

from collections import deque

def levelOrder(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        current_level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(current_level)
    
    return result

复杂度分析： - 时间复杂度：O(N)，其中N是二叉树的节点数。每个节点被访问一次。 - 空间复杂度：O(M)，其中M是二叉树的最大宽度（即某一层的最大节点数）。

2.2 岛屿数量（LeetCode 200）

题目描述：给定一个由 ‘1’（陆地）和 ‘0’（水）组成的二维网格，计算岛屿的数量。岛屿被水包围，并且通过水平或垂直方向上相邻的陆地连接而成。

示例：

输入：
[
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

解题思路： - 遍历整个网格，当遇到 ‘1’ 时，启动BFS，标记所有与之相连的 ‘1’，表示一个岛屿。 - 每次启动BFS时，岛屿数量加1。

代码实现：

from collections import deque

def numIslands(grid):
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    num_islands = 0
    
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':
                num_islands += 1
                grid[i][j] = '0'  # 标记为已访问
                queue = deque([(i, j)])
                
                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':
                            grid[nx][ny] = '0'
                            queue.append((nx, ny))
    
    return num_islands

复杂度分析： - 时间复杂度：O(M×N)，其中M和N分别是网格的行数和列数。每个网格点最多被访问一次。 - 空间复杂度：O(min(M, N))，在最坏情况下，队列的大小可能达到网格的最小维度。

2.3 打开转盘锁（LeetCode 752）

题目描述：你有一个带有四个圆形拨轮的转盘锁。每个拨轮有10个数字：’0’到’9’。每个拨轮可以自由旋转：例如把’9’变为’0’，’0’变为’9’。每次旋转只能将一个拨轮旋转一个位置。锁的初始数字为’0000’，给定一个目标数字和一个禁止列表，计算从初始数字到目标数字的最少旋转次数。如果无法达到目标数字，返回-1。

示例：

输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。

解题思路： - 使用BFS从初始状态’0000’开始，逐层遍历所有可能的密码组合。 - 每次旋转一个拨轮，生成新的密码组合，并检查是否为目标密码或禁止密码。 - 如果遇到禁止密码，则跳过；如果遇到目标密码，则返回当前层数。

代码实现：

from collections import deque

def openLock(deadends, target):
    dead_set = set(deadends)
    if "0000" in dead_set:
        return -1
    
    queue = deque([("0000", 0)])
    visited = set("0000")
    
    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_set:
                    visited.add(new_state)
                    queue.append((new_state, steps + 1))
    
    return -1

复杂度分析： - 时间复杂度：O(N^2 × A^N)，其中N是密码的长度（4），A是每个拨轮的可能取值（10）。最坏情况下需要遍历所有可能的密码组合。 - 空间复杂度：O(A^N)，用于存储访问过的密码组合。

3. 总结

广度优先搜索算法在LeetCode中的应用非常广泛，尤其适用于解决最短路径、连通性等问题。通过本文的分析，我们可以看到BFS在二叉树层序遍历、岛屿数量计算以及转盘锁问题中的具体应用。掌握BFS算法的核心思想和实现方法，能够帮助我们更高效地解决类似的算法问题。