算法-BFS

前言

广度优先搜索（Breadth-First Search，简称BFS）是一种用于遍历或搜索树或图的算法。与深度优先搜索不同，BFS 从源节点开始，首先访问所有邻近节点，然后才移动到下一层节点。

BFS 算法基本原理

BFS 使用队列数据结构来跟踪需要访问的节点：

将起始节点放入队列中
当队列不为空时：
- 取出队列头部节点并访问
- 将该节点的所有未访问的邻居节点加入队列
- 标记这些邻居节点为已访问

BFS 代码模板

from collections import deque

def bfs(graph, start):
    # 创建队列并将起始节点加入队列
    queue = deque([start])
    # 使用集合记录已访问的节点
    visited = {start}
    
    while queue:
        # 取出队列头部节点
        node = queue.popleft()
        print(node)  # 处理当前节点
        
        # 遍历当前节点的所有邻居
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

BFS 的时间和空间复杂度

时间复杂度：$O(V + E)$，其中 $V$ 是节点数，$E$ 是边数
空间复杂度：$O(V)$，最坏情况下，队列中可能包含所有节点

BFS 在 LeetCode 中的应用

1. 二叉树层序遍历 (LeetCode 102)

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

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

2. 岛屿数量 (LeetCode 200)

def numIslands(grid):
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    count = 0
    
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':
                count += 1
                # 使用BFS将相连的陆地都标记为已访问
                bfs_island(grid, i, j)
    
    return count

def bfs_island(grid, i, j):
    rows, cols = len(grid), len(grid[0])
    queue = deque([(i, j)])
    grid[i][j] = '0'  # 标记为已访问
    
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    while queue:
        r, c = queue.popleft()
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1'):
                queue.append((nr, nc))
                grid[nr][nc] = '0'  # 标记为已访问

3. 单词接龙 (LeetCode 127)

def ladderLength(beginWord, endWord, wordList):
    word_set = set(wordList)
    if endWord not in word_set:
        return 0
    
    queue = deque([(beginWord, 1)])  # (word, level)
    visited = {beginWord}
    
    while queue:
        current_word, level = queue.popleft()
        
        # 尝试更改当前单词的每一个位置
        for i in range(len(current_word)):
            # 尝试用26个小写字母替换
            for c in 'abcdefghijklmnopqrstuvwxyz':
                next_word = current_word[:i] + c + current_word[i+1:]
                
                if next_word == endWord:
                    return level + 1
                
                if next_word in word_set and next_word not in visited:
                    visited.add(next_word)
                    queue.append((next_word, level + 1))
    
    return 0

4. 腐烂的橘子 (LeetCode 994)

def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh_count = 0
    
    # 找出所有腐烂的橘子和新鲜橘子的数量
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 2:
                queue.append((i, j, 0))  # (row, col, minutes)
            elif grid[i][j] == 1:
                fresh_count += 1
    
    if fresh_count == 0:
        return 0
    
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    max_minutes = 0
    
    while queue:
        r, c, minutes = queue.popleft()
        max_minutes = max(max_minutes, minutes)
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1):
                grid[nr][nc] = 2
                fresh_count -= 1
                queue.append((nr, nc, minutes + 1))
    
    return max_minutes if fresh_count == 0 else -1

BFS 的优缺点

优点

保证找到最短路径（对于无权图）
适合寻找最少步骤的问题
对于层次遍历非常有效

缺点

相比DFS，内存消耗更大
对于很宽的图，可能会占用大量内存
不适合搜索目标较深且分支很多的情况

后记

BFS 是一种强大的图遍历算法，特别适合解决最短路径、层次遍历等问题。在 LeetCode 中，BFS 常用于解决图、树的遍历问题，以及迷宫类、变换类的问题。掌握 BFS 可以帮助我们更高效地解决许多复杂问题。