数据结构与算法 / 系统课时
用队列分层完成最短步数搜索
用队列分层完成最短步数搜索
只要每次移动的代价都相同,最少操作次数、迷宫最短步数和状态扩散问题通常都能改写成无权图最短路。BFS 用队列按距离一层层扩展状态,第一个到达目标的层就是最短距离;关键是正确维护层数,并在入队时立即做访问标记。
学习目标
- 能把网格、字符串变化或操作序列问题抽象成 BFS 状态图
- 理解队列为什么天然按照距离从小到大访问节点
- 掌握分层计数和访问标记的正确时机,避免重复搜索
为什么 BFS 能保证最短步数
把一个状态看成图中的节点,把一次合法操作看成一条边。如果所有边的代价都相同,那么从起点出发,一次操作可达的节点属于第 1 层,两次操作可达且尚未访问的节点属于第 2 层,依次向外扩散。
FIFO 队列保证第 层的节点全部出队并扩展后,才会轮到第 层。因此某个状态第一次被访问时,已经找到了从起点到它的最少步数,不需要以后再用更长路径更新它。

层数应该怎样维护
常见做法有两种。第一种是在队列元素中直接保存 (状态, 距离);第二种是每轮先读取当前队列长度,把这一批节点视作同一层,处理完后统一让层数加一。
如果题目只要求最短距离,两种方法都正确。状态本身还需要携带钥匙数量、剩余消除次数等额外信息时,把距离或完整状态一起放入队列通常更直观;如果题目强调逐层扩散,例如腐烂橘子或二叉树层序遍历,按当前队列长度划层更自然。
用 BFS 求网格最短步数
下面把二维网格中的可通行位置看成节点,上下左右移动看成代价相同的边。0 表示可通行,1 表示障碍,从左上角搜索到右下角。
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))预期输出:
6输出 6 表示从 (0, 0) 到 (3, 3) 最少需要移动 6 次。若队列耗尽仍没有访问到目标,函数返回 -1。
访问标记要在入队时完成
BFS 最常见的性能错误,是等节点出队时才加入 visited。假设同一个未访问节点同时与当前层的多个节点相邻,它就可能在真正出队前被重复加入队列多次,状态空间较大时会造成明显的时间和内存浪费。
正确规则是:一旦确认某个状态合法并准备入队,就立刻标记为已访问。因为无权图 BFS 第一次发现它时已经走的是最短路径,之后其他路径没有必要再次把它加入队列。
如果一个位置在不同附加状态下仍可能产生不同答案,例如“坐标相同但剩余消除障碍次数不同”,访问标记就不能只保存坐标,而应保存完整状态,如 (row, col, remaining)。这类题真正决定 BFS 是否正确的,往往不是队列写法,而是“什么才算同一个状态”。
复杂度与适用边界
设状态图有 个可访问状态、 条合法转移。每个状态最多入队一次,每条边最多被检查常数次,因此时间复杂度为 ,队列和访问集合的空间复杂度为 。
BFS 的最短路保证依赖于每条边代价相同。普通带权图不能直接用层数表示距离,应改用 Dijkstra 等算法;边权只有 0 和 1 时,可以进一步使用 0-1 BFS。遇到“最少几步”“最少操作次数”“最早多久扩散到全部节点”时,先检查能否把问题表示成状态、等代价转移、起点和目标条件,通常就能判断是否适合使用分层 BFS。