数据结构与算法 / 系统课时
BFS 怎么求无权最短步数
BFS 怎么求无权最短步数
无权图里每条边都可以看成一次等成本移动。BFS 通过队列按距离一层层扩展节点,因此第一次到达某个节点时,就已经得到从起点到它的最少边数。本节用一个完整示例把“分层、标记、距离更新”串起来。
学习目标
- 理解 BFS 为什么能保证无权图中的最短步数
- 用队列和距离数组写出可直接运行的最短路代码
- 判断不可达、起终点相同等常见边界
为什么 BFS 第一次到达就是最短
从起点开始,BFS 先处理距离为 0 的起点,再处理所有距离为 1 的节点,然后才会进入距离为 2、3 的节点。队列的先进先出顺序保证了这种分层关系不会被打乱。
如果当前节点 u 的最短距离已经确定为 dist[u],那么第一次发现相邻且未访问的节点 v 时,可以直接令 。因为所有边代价都相同,不可能存在一条需要更多层之后才出现、却边数更少的路径。

用距离数组同时完成访问标记
最稳妥的写法是把距离数组初始化为 -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,但邻接表必须只保留允许行走的方向。
复杂度和适用边界
使用邻接表时,每个节点最多入队一次,每条边只会被检查常数次,因此时间复杂度是 ,额外的距离数组和队列最多保存 个节点。
BFS 适用于每条边代价相同的最短步数问题,例如迷宫最少移动次数、社交关系最少跳数、状态转换最少操作次数。只要不同边的代价不再相同,“按层数最少”就不等于“总代价最小”,这时应改用适合加权图的最短路算法。
按自己的节奏,确认真正理解。