Python实现广度优先搜索（BFS）：遍历路径与最短路径问题

你的代码里有两处需要调整：一是字典graph重复定义了'J'键（虽不影响J被访问，但属于冗余代码）；二是现有BFS仅实现节点遍历打印，没有路径记录逻辑，无法获取S到J的最短路径。

以下是修正后的代码，同时实现遍历打印和最短路径查找功能：

graph = {
    'S': ['A', 'B', 'C'],
    'A': ['D'],
    'B': ['E'],
    'C': ['F', 'J'],
    'D': ['G'],
    'E': ['I', 'J'],
    'F': ['S'],
    'J': [],
    'G': ['H'],
    'I': [],
    'H': ['D']
}

def bfs(graph, start, target):
    visited = []
    queue = [start]
    visited.append(start)
    # 记录每个节点的前驱，用于回溯路径
    predecessor = {start: None}

    while queue:
        current_node = queue.pop(0)
        print(current_node, end=" ")

        # 找到目标节点后提前终止遍历
        if current_node == target:
            break

        for neighbor in graph[current_node]:
            if neighbor not in visited:
                visited.append(neighbor)
                queue.append(neighbor)
                predecessor[neighbor] = current_node

    # 回溯生成最短路径
    path = []
    current = target
    while current is not None:
        path.append(current)
        current = predecessor.get(current)
    path.reverse()

    return path if target in visited else None

# 执行BFS并输出结果
print("广度优先遍历顺序：")
shortest_path = bfs(graph, 'S', 'J')
print("\nS到J的最短路径：", shortest_path)

代码说明 #

1. 规范字典结构：移除了graph中重复的'J'键定义，保证数据结构合法。
2. 前驱节点追踪：用predecessor字典存储每个节点的上一级访问节点，为路径回溯提供依据。
3. 遍历优化：当遍历到目标节点J时直接终止循环，减少不必要的计算。
4. 路径生成：从J倒推回起始节点S，再反转得到正序的最短路径。

运行结果示例：

广度优先遍历顺序：
S A B C D E F J 
S到J的最短路径： ['S', 'C', 'J']

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