图的广度优先最短路径

功能说明

shortest_path 在无权图上执行广度优先搜索。它用双端队列按层扩展节点，首次访问某个节点时记录父节点；一旦遇到目标就沿父指针回溯，得到边数最少的路径。若队列耗尽仍未到达目标，返回 None 表示不可达；起点不在图中则抛出 KeyError。

关键代码

queue: deque[Node] = deque([start])
parent: dict[Node, Node | None] = {start: None}
while queue:
    node = queue.popleft()
    for neighbor in graph.get(node, ()):
        if neighbor in parent:
            continue
        parent[neighbor] = node
        if neighbor == goal:
            return reconstruct(parent, goal)
        queue.append(neighbor)

parent 同时承担“已访问”集合的职责，避免重复入队和额外的 visited 集合。

使用注意

• 只适用于边权相同或无权图；带权图应使用 Dijkstra 或 Bellman-Ford。
• 邻接表允许目标节点没有出边，graph.get(node, ()) 会安全返回空序列。
• 节点必须是可哈希对象；如果节点是列表或字典，需要先转成元组或 ID。
• 返回路径包含起点和终点；起点等于终点时直接返回单元素列表。
• BFS 找到的只是其中一条最短路径，多条等长路径时取决于邻接表顺序。

验证方式

示例中 a 到 f 应返回 ['a', 'c', 'e', 'f'] 或另一条等长路径；island 不可达返回 None；起点 missing 会抛出带节点名的 KeyError。可以调整邻接表顺序，确认路径长度不变。