求基于广度优先搜索（BFS）的图最短路径实现代码

要通过BFS求解图的最短路径，核心是记录每个节点的前驱节点，当找到目标节点后，通过回溯前驱节点就能得到从起点到目标的最短路径。以下是针对你提供的图的实现代码：

graph = {
    'S' : ['A','B'],
    'A' : ['B','C','D'],
    'B' : ['C'],
    'C' : ['D'],
    'D' : []
}

def bfs_shortest_path(graph, start, goal):
    # 记录已访问节点，避免重复遍历
    visited = []
    # 队列存储待遍历的节点
    queue = [start]
    # 记录每个节点的前驱，用于回溯路径
    parent = {start: None}

    while queue:
        current_node = queue.pop(0)
        
        # 找到目标节点，回溯路径
        if current_node == goal:
            path = []
            while current_node is not None:
                path.append(current_node)
                current_node = parent[current_node]
            # 反转路径得到从起点到目标的顺序
            return path[::-1]
        
        if current_node not in visited:
            visited.append(current_node)
            # 遍历所有邻居节点
            for neighbor in graph[current_node]:
                if neighbor not in visited and neighbor not in parent:
                    parent[neighbor] = current_node
                    queue.append(neighbor)
    
    # 如果目标节点不可达，返回空路径
    return []

# 调用函数并输出结果
start_node = 'S'
goal_node = 'D'
shortest_path = bfs_shortest_path(graph, start_node, goal_node)
print(f"从 {start_node} 到 {goal_node} 的最短路径: {shortest_path}")

代码说明： #

• parent字典：用于记录每个节点的前驱节点，比如parent['A'] = 'S'表示节点A是从S过来的，这是回溯路径的核心依据。
• 目标节点处理：当遍历到目标节点时，立即通过parent字典倒推回起点，再反转得到正序的最短路径——BFS的层级遍历特性天然保证首次到达目标节点的路径就是最短路径。
• 重复处理规避：通过visited和parent双重判断，确保每个节点只被处理一次，避免无效遍历。

运行上述代码，输出结果为：从 S 到 D 的最短路径: ['S', 'A', 'D']，这就是该图中S到D的最短路径。

内容的提问来源于stack exchange，提问作者vernonnn