广度优先搜索（BFS）在LeetCode中的应用

广度优先搜索（Breadth-First Search, BFS）是一种图论中的搜索算法，常用于解决最短路径问题、网络流问题以及树的层序遍历等。在LeetCode平台上，BFS算法是许多题目的核心解题思路。本文将详细介绍BFS在LeetCode中的应用，并列举一些经典题目。

BFS算法简介

BFS的核心思想是从一个节点开始，逐层访问其相邻节点，直到找到目标节点或遍历完所有节点。它的实现通常使用队列（Queue）来辅助，保证先进先出的顺序访问节点。以下是BFS的基本步骤：

初始化队列：将起始节点加入队列。
标记节点：将起始节点标记为已访问。
循环：
- 从队列中取出一个节点。
- 访问该节点的相邻节点。
- 将未访问的相邻节点加入队列并标记为已访问。
重复步骤3，直到队列为空或找到目标节点。

LeetCode中的BFS应用

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

这是一个经典的BFS应用题目。题目要求按层输出二叉树的节点值。使用BFS可以很自然地实现这一需求：

from collections import deque

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

2. 最短路径问题（LeetCode 752）

题目要求找到打开锁的最少旋转次数。BFS可以有效地找到最短路径：

from collections import deque

def openLock(deadends, target):
    dead = set(deadends)
    if "0000" in dead:
        return -1
    queue = deque([("0000", 0)])
    visited = set("0000")
    while queue:
        node, steps = queue.popleft()
        if node == target:
            return steps
        for i in range(4):
            for d in (-1, 1):
                new_node = node[:i] + str((int(node[i]) + d) % 10) + node[i+1:]
                if new_node not in dead and new_node not in visited:
                    visited.add(new_node)
                    queue.append((new_node, steps + 1))
    return -1

3. 图的连通性（LeetCode 200）

题目要求计算岛屿的数量。BFS可以用来遍历每个岛屿：

from collections import deque

def numIslands(grid):
    if not grid:
        return 0
    m, n = len(grid), len(grid[0])
    count = 0
    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 [(1,0), (-1,0), (0,1), (0,-1)]:
                        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

总结

广度优先搜索（BFS）在LeetCode中有着广泛的应用，它不仅能解决最短路径问题，还适用于树的层序遍历、图的连通性检查等。通过理解BFS的基本原理和应用场景，开发者可以更有效地解决算法问题。希望通过本文的介绍，大家能对BFS在LeetCode中的应用有更深入的理解，并在实际编程中灵活运用。