数据结构与算法 / 系统课时

用队列分层完成最短步数搜索

用队列分层完成最短步数搜索

只要每次移动的代价都相同,最少操作次数、迷宫最短步数和状态扩散问题通常都能改写成无权图最短路。BFS 用队列按距离一层层扩展状态,第一个到达目标的层就是最短距离;关键是正确维护层数,并在入队时立即做访问标记。

学习目标

  • 能把网格、字符串变化或操作序列问题抽象成 BFS 状态图
  • 理解队列为什么天然按照距离从小到大访问节点
  • 掌握分层计数和访问标记的正确时机,避免重复搜索

为什么 BFS 能保证最短步数

把一个状态看成图中的节点,把一次合法操作看成一条边。如果所有边的代价都相同,那么从起点出发,一次操作可达的节点属于第 1 层,两次操作可达且尚未访问的节点属于第 2 层,依次向外扩散。

FIFO 队列保证第 dd 层的节点全部出队并扩展后,才会轮到第 d+1d+1 层。因此某个状态第一次被访问时,已经找到了从起点到它的最少步数,不需要以后再用更长路径更新它。

BFS 按层扩散并得到最短步数

层数应该怎样维护

常见做法有两种。第一种是在队列元素中直接保存 (状态, 距离);第二种是每轮先读取当前队列长度,把这一批节点视作同一层,处理完后统一让层数加一。

如果题目只要求最短距离,两种方法都正确。状态本身还需要携带钥匙数量、剩余消除次数等额外信息时,把距离或完整状态一起放入队列通常更直观;如果题目强调逐层扩散,例如腐烂橘子或二叉树层序遍历,按当前队列长度划层更自然。

用 BFS 求网格最短步数

下面把二维网格中的可通行位置看成节点,上下左右移动看成代价相同的边。0 表示可通行,1 表示障碍,从左上角搜索到右下角。

python
from collections import deque


def shortest_steps(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    start = (0, 0)
    target = (rows - 1, cols - 1)

    if grid[0][0] == 1 or grid[target[0]][target[1]] == 1:
        return -1

    queue = deque([(0, 0, 0)])
    visited = {start}
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    while queue:
        row, col, distance = queue.popleft()
        if (row, col) == target:
            return distance

        for dr, dc in directions:
            nr, nc = row + dr, col + dc
            # 只把边界内、可通行且从未入队的状态加入下一层。
            if 0 <= nr < rows and 0 <= nc < cols:
                if grid[nr][nc] == 0 and (nr, nc) not in visited:
                    visited.add((nr, nc))
                    queue.append((nr, nc, distance + 1))

    return -1


if __name__ == "__main__":
    grid = [
        [0, 0, 1, 0],
        [1, 0, 0, 0],
        [1, 1, 0, 1],
        [0, 0, 0, 0],
    ]
    print(shortest_steps(grid))

预期输出:

text
6

输出 6 表示从 (0, 0) 到 (3, 3) 最少需要移动 6 次。若队列耗尽仍没有访问到目标,函数返回 -1。

访问标记要在入队时完成

BFS 最常见的性能错误,是等节点出队时才加入 visited。假设同一个未访问节点同时与当前层的多个节点相邻,它就可能在真正出队前被重复加入队列多次,状态空间较大时会造成明显的时间和内存浪费。

正确规则是:一旦确认某个状态合法并准备入队,就立刻标记为已访问。因为无权图 BFS 第一次发现它时已经走的是最短路径,之后其他路径没有必要再次把它加入队列。

如果一个位置在不同附加状态下仍可能产生不同答案,例如“坐标相同但剩余消除障碍次数不同”,访问标记就不能只保存坐标,而应保存完整状态,如 (row, col, remaining)。这类题真正决定 BFS 是否正确的,往往不是队列写法,而是“什么才算同一个状态”。

复杂度与适用边界

设状态图有 VV 个可访问状态、EE 条合法转移。每个状态最多入队一次,每条边最多被检查常数次,因此时间复杂度为 O(V+E)O(V + E),队列和访问集合的空间复杂度为 O(V)O(V)。

BFS 的最短路保证依赖于每条边代价相同。普通带权图不能直接用层数表示距离,应改用 Dijkstra 等算法;边权只有 0 和 1 时,可以进一步使用 0-1 BFS。遇到“最少几步”“最少操作次数”“最早多久扩散到全部节点”时,先检查能否把问题表示成状态、等代价转移、起点和目标条件,通常就能判断是否适合使用分层 BFS。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用队列分层完成最短步数搜索

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通