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

图的广度优先遍历

图的广度优先遍历

图的广度优先遍历适合按“离起点有多远”逐层搜索。本课将用队列完成遍历,并在无权图中记录距离与前驱,最终得到从起点到目标节点的最少边数和一条对应路径。

学习目标

  • 理解 BFS 的分层扩展机制与入队标记原则
  • 使用距离表和前驱表求解无权图最短路径
  • 分析邻接表实现的时间、空间复杂度与不可达边界

问题定义与适用条件

给定一个无权图、起点和目标点,需要找到经过边数最少的路径。BFS 每次先处理距离起点更近的节点,因此某个节点第一次被发现时,已经获得最少边数。

这里的“无权”也包括所有边权相同的情况。若不同边的代价不同,BFS 不能保证总代价最小,应改用 Dijkstra 等算法。

BFS 分层扩展与前驱路径

分层遍历机制

队列保证先入队的节点先处理。起点先以距离 0 入队;处理当前节点时,只把尚未发现的邻居加入队列,并把邻居距离设置为当前距离加 1。

访问标记必须在入队时完成,而不是等到出队。否则同一节点可能被多个前驱重复加入队列,既浪费空间,也会让前驱记录变得混乱。

前驱表保存“这个节点第一次从哪里到达”。找到目标后,从目标沿前驱反向回溯到起点,再反转序列即可还原路径。存在多条最短路径时,结果取决于邻接表中的邻居顺序。

主示例:求最少边数与路径

python
from collections import deque
from typing import Optional

def shortest_path(
    graph: dict[str, list[str]],
    start: str,
    target: str,
) -> tuple[Optional[int], Optional[list[str]]]:
    if start not in graph or target not in graph:
        raise ValueError("起点和目标点必须存在于图中")

    queue = deque([start])
    distance = {start: 0}
    previous: dict[str, Optional[str]] = {start: None}

    while queue:
        current = queue.popleft()
        if current == target:
            break

        for neighbor in graph[current]:
            # 入队时立即标记,避免同一节点重复进入队列
            if neighbor not in distance:
                distance[neighbor] = distance[current] + 1
                previous[neighbor] = current
                queue.append(neighbor)

    if target not in distance:
        return None, None

    path = []
    current: Optional[str] = target
    while current is not None:
        path.append(current)
        current = previous[current]

    path.reverse()
    return distance[target], path

graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}

distance, path = shortest_path(graph, "A", "F")
print("最短距离:", distance)
print("最短路径:", path)

预期输出:

text
最短距离: 2
最短路径: ['A', 'C', 'F']

复杂度与关键边界

使用邻接表时,每个可达节点至多入队一次,每条边至多被扫描一次,时间复杂度为 O(V+E)O(V+E),距离表、前驱表和队列的空间复杂度为 O(V)O(V)。

目标不可达时应返回空结果,而不是强行回溯。对于非连通图,从一个起点执行 BFS 只会访问该连通分量;若要遍历整张图,需要从每个尚未访问的节点重新启动一次 BFS。

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

目录与阅读设置

阅读设置

17

记录一个想法

图的广度优先遍历

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

登录哪都通