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

BFS 怎么求无权最短步数

BFS 怎么求无权最短步数

无权图里每条边都可以看成一次等成本移动。BFS 通过队列按距离一层层扩展节点,因此第一次到达某个节点时,就已经得到从起点到它的最少边数。本节用一个完整示例把“分层、标记、距离更新”串起来。

学习目标

  • 理解 BFS 为什么能保证无权图中的最短步数
  • 用队列和距离数组写出可直接运行的最短路代码
  • 判断不可达、起终点相同等常见边界

为什么 BFS 第一次到达就是最短

从起点开始,BFS 先处理距离为 0 的起点,再处理所有距离为 1 的节点,然后才会进入距离为 2、3 的节点。队列的先进先出顺序保证了这种分层关系不会被打乱。

如果当前节点 u 的最短距离已经确定为 dist[u],那么第一次发现相邻且未访问的节点 v 时,可以直接令 dist[v]=dist[u]+1dist[v]=dist[u]+1。因为所有边代价都相同,不可能存在一条需要更多层之后才出现、却边数更少的路径。

BFS 按层扩展并确定无权最短步数

用距离数组同时完成访问标记

最稳妥的写法是把距离数组初始化为 -1,同时让它承担“是否访问过”的职责。起点距离设为 0;发现新节点时立即写入距离并入队,而不是等它出队后再标记。

“入队时标记”很重要。若两个节点都连向同一个未标记节点,而代码等到出队才标记,这个节点可能被重复加入队列,既增加开销,也会让后续逻辑更难维护。

一个可运行的最短步数示例

下面的无向图从 A 走到 F,两条最短路线都需要 3 条边。代码在目标节点第一次出队时返回距离;如果队列耗尽仍未到达目标,则返回 -1。

python
from collections import deque

def shortest_steps(graph, start, target):
    if start not in graph or target not in graph:
        return -1

    dist = {node: -1 for node in graph}
    dist[start] = 0
    queue = deque([start])

    while queue:
        node = queue.popleft()
        if node == target:
            return dist[node]

        for neighbor in graph[node]:
            if dist[neighbor] != -1:
                continue
            # 第一次发现节点时,上一层距离加 1 就是它的最短步数。
            dist[neighbor] = dist[node] + 1
            queue.append(neighbor)

    return -1

def main():
    graph = {
        "A": ["B", "C"],
        "B": ["A", "D"],
        "C": ["A", "D", "E"],
        "D": ["B", "C", "F"],
        "E": ["C", "F"],
        "F": ["D", "E"],
    }

    print(shortest_steps(graph, "A", "F"))

if __name__ == "__main__":
    main()

预期输出

text
3

如果 start == target,返回值自然是 0;如果目标位于另一个连通分量,最终返回 -1。对于有向图,同样可以使用 BFS,但邻接表必须只保留允许行走的方向。

复杂度和适用边界

使用邻接表时,每个节点最多入队一次,每条边只会被检查常数次,因此时间复杂度是 O(V+E)O(V+E),额外的距离数组和队列最多保存 O(V)O(V) 个节点。

BFS 适用于每条边代价相同的最短步数问题,例如迷宫最少移动次数、社交关系最少跳数、状态转换最少操作次数。只要不同边的代价不再相同,“按层数最少”就不等于“总代价最小”,这时应改用适合加权图的最短路算法。

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

目录与阅读设置

阅读设置

17

记录一个想法

BFS 怎么求无权最短步数

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

登录哪都通