广度优先搜索 BFS：最短路径与层序遍历

FreeGuideOnline 最新 2026-06-18

什么是广度优先搜索

广度优先搜索（Breadth-First Search，简称 BFS）是一种用于树或图数据结构的遍历算法。它从一个起始节点开始，先访问其所有相邻节点，然后再按访问顺序依次访问这些相邻节点的相邻节点，一层一层向外扩展，就像水波扩散一样。

BFS 的核心思想可以概括为两点：

层序遍历：在树中，BFS 会从上到下、从左到右逐层访问节点。
最短路径：在无权图中，BFS 保证从起点到任意可达节点的路径长度是最短的。

为了实现“先访问的节点，其邻居先被扩展”，BFS 使用队列这种先进先出的数据结构。

BFS 的工作原理

BFS 的执行过程可以分解为以下步骤：

将起始节点放入队列，并标记为已访问。
当队列不为空时，重复以下操作：
- 从队列头部取出一个节点（称为当前节点）。
- 访问该节点（例如打印其值或记录信息）。
- 遍历当前节点的所有未访问的邻居节点，将它们依次加入队列，并标记为已访问。
队列为空时，说明所有与起点连通的节点都已被访问，算法结束。

通过标记已访问节点，可以避免重复处理以及死循环（尤其在图中存在回路时）。

BFS 的两种典型应用

1. 层序遍历（树结构）

在二叉树中，BFS 可以完美实现层序遍历，即按层次依次输出节点值。例如，对于下方的二叉树：

层序遍历的结果为：1 2 3 4 5 6。

实现时，只需将根节点入队，然后不断出队并让左右孩子入队即可。

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def level_order(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. 最短路径（无权图）

对于边权为 1 的图（或所有边权相等的情况），BFS 能够找到从起点到目标节点的最短路径，即经过的边数最少。

BFS 访问节点的顺序恰好对应从起点出发步数的递增。第一次到达某个节点时走的路径，一定就是最短路径。

典型例题：在一个网格迷宫中，0 表示空地，1 表示障碍物，求从左上角到右下角的最短步数。

from collections import deque

def shortest_path_in_grid(grid):
    if not grid or not grid[0]:
        return -1
    rows, cols = len(grid), len(grid[0])
    if grid[0][0] == 1 or grid[rows-1][cols-1] == 1:
        return -1

    directions = [(1,0), (-1,0), (0,1), (0,-1)]
    queue = deque([(0, 0, 0)])  # (row, col, distance)
    visited = [[False] * cols for _ in range(rows)]
    visited[0][0] = True

    while queue:
        r, c, dist = queue.popleft()
        if r == rows - 1 and c == cols - 1:
            return dist
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc] and grid[nr][nc] == 0:
                visited[nr][nc] = True
                queue.append((nr, nc, dist + 1))
    return -1

在这个示例中，一旦目标节点被弹出队列，当前的 dist 就是最短距离。

BFS 的复杂度分析

时间复杂度：O(V + E)
其中 V 是节点数，E 是边数。在邻接表表示下，每个节点和每条边都会被处理常数次。
空间复杂度：O(V)
队列中最多可能存放所有节点，同时需要额外的 visited 数组记录访问状态。

对于网格类问题，V 和 E 与网格大小成正比，复杂度通常记为 O(行数 × 列数)。

BFS 模板代码（Python）

下面提供一个通用的 BFS 模板，适用于大多数问题：

from collections import deque

def bfs(start, graph):
    queue = deque([start])
    visited = set([start])   # 或者用数组/字典
    while queue:
        node = queue.popleft()
        # 处理当前节点 (node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

如果要求记录路径长度或层级信息，可以在入队时携带步数，或者像层序遍历那样按层处理。

常见变体与注意事项

双向 BFS
当起点和终点已知且图无向时，可以同时从起点和终点进行 BFS，两者相遇时即找到最短路径，能显著减少搜索空间。
多源 BFS
初始时将多个起点同时入队，常用于求解多个起点到各个位置的最短距离（例如病毒扩散模型）。
BFS 与 DFS 的对比
- DFS 使用栈（递归本质也是栈），适合寻找所有路径、连通性判断等问题。
- BFS 使用队列，适合最短路径、层序遍历等场景。
- 在树中，DFS 按深度优先，BFS 按广度优先。
避免重复访问
必须在入队时立即标记为已访问，而不是在出队时再标记。否则，同一个节点可能被多次加入队列，导致性能下降甚至无限循环。

实际练习建议

光看理论是不够的，建议通过以下经典问题巩固 BFS：

二叉树的层序遍历（LeetCode 102）
岛屿数量（LeetCode 200）
打开转盘锁（LeetCode 752）
单词接龙（LeetCode 127）
腐烂的橘子（LeetCode 994）

动手实现时注意：

选用合适的数据结构 (deque 比 list 的 pop(0) 高效得多)。
根据题目决定队列中存储的信息（坐标、步数、状态等）。
检查边界条件，防止越界或空输入。

广度优先搜索是算法基础中的核心工具，掌握了它，你就拥有了解决大量搜索和最短路径问题的利器。反复练习模板与变体，你将能熟练应用到各类场景中。