BFS求最短路径的两种实现方式，哪种综合性能更具优势？

BFS查找两节点间最短路径主要有两种实现思路：第一种是使用嵌套列表的队列结构存储遍历路径，第二种是维护每个节点到其父节点的映射，遍历邻接节点时记录父节点，最终通过回溯父节点映射得到完整路径。

具体实现代码 #

第一种：路径队列实现 #

def bfs(graph, start, end):
    # 维护存储路径的队列
    queue = []
    # 将起始路径推入队列
    queue.append([start])
    while queue:
        # 取出队列中第一条路径
        path = queue.pop(0)
        # 取路径的最后一个节点
        node = path[-1]
        # 找到目标路径直接返回
        if node == end:
            return path
        # 遍历所有邻接节点，构造新路径推入队列
        for adjacent in graph.get(node, []):
            new_path = list(path)
            new_path.append(adjacent)
            queue.append(new_path)

print(bfs(graph, 'A', 'F'))

第二种：父节点映射+回溯实现 #

def backtrace(parent, start, end):
    path = [end]
    while path[-1] != start:
        path.append(parent[path[-1]])
    path.reverse()
    return path
        
def bfs(graph, start, end):
    parent = {}
    queue = []
    queue.append(start)
    while queue:
        node = queue.pop(0)
        if node == end:
            return backtrace(parent, start, end)
        for adjacent in graph.get(node, []):
            if node not in queue :
                parent[adjacent] = node # 记录邻接节点的父节点
                queue.append(adjacent)

print(bfs(graph, 'A', 'F'))

测试用有向图 #

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

问题解答 #

1. 第二种方式是否在各方面都优于第一种？ #

答案是否定的，两种实现的适用场景有明显区别：

• 第二种仅适用于查找单条最短路径的场景，如果需求是查找两节点之间所有的最短路径，第二种实现无法满足：父节点映射默认每个节点仅存储一个父节点，会丢失其他相同长度路径的父节点关联关系，无法回溯得到所有最短路径。而第一种路径队列实现仅需要在第一次找到终点时不直接返回，遍历完当前层所有节点即可收集全部最短路径。
• 给出的第二种实现本身存在逻辑缺陷：if node not in queue的判断条件错误，正确逻辑应该是判断邻接节点是否已经被访问过，否则存在环的图会出现重复入队死循环的问题，同时也会进一步丢失多路径场景下的父节点记录。

2. 能否将第二种方式视为第一种基础版BFS的优化实现？ #

仅针对「查找单条最短路径」的场景，可以将第二种视为第一种的优化实现：

• 空间优势非常明显：第一种队列存储全路径，最坏情况下空间复杂度为O(b^d)，其中b是节点平均分支数，d是最短路径长度，在大图或路径较长的场景下内存开销会指数级增长；第二种的队列和父节点映射空间复杂度均为稳定的O(V)（V为顶点总数），内存开销可控。
• 时间效率差异极小：两种实现的核心遍历时间复杂度均为O(V+E)，第二种仅多出O(d)的回溯开销，几乎可以忽略。
  如果场景扩展到查找所有最短路径、所有简单路径，第二种实现无法适配，自然谈不上是第一种的优化。

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