BFS寻找最短路径的两种实现方法，哪一种是明显的赢家？

Question

有两种方法可以实现 BFS 以找到两个节点之间的最短路径。第一种是使用列表的列表来表示路径队列。另一种是维护每个节点到其父节点的映射，并在检查相邻节点时记录其父节点，最后根据父节点映射进行回溯以找到路径。（查看此 post 了解更多详情。。感谢 qiao 对该问题的回答和代码！）

复制到这里：第一种方式：

def bfs(graph, start, end):
    # maintain a queue of paths
    queue = []
    # push the first path into the queue
    queue.append([start])
    while queue:
        # get the first path from the queue
        path = queue.pop(0)
        # get the last node from the path
        node = path[-1]
        # path found
        if node == end:
            return path
        # enumerate all adjacent nodes, construct a 
        # new path and push it into the queue
        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 # <<<<< record its parent 
                queue.append(adjacent)

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

和图（有向图）

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

我们可以看到第二种方式可以节省内存成本，因为队列不需要存储路径，space队列和父映射的复杂度都是O(V)，其中V 是顶点数。而且，最终的回溯过程最多花费额外的 O(V) 时间。

那么，在寻找有向图中两个节点之间的最短路径或所有路径时，第二种方式是否在所有方面都优于第一种方式？我们能不能把第二种看作是BFS基础版的优化（第一种方式）？

Answer 1

第二个版本更好。这是因为内存分配也需要时间。即这一行：

new_path = list(path)

...就path的长度而言，时间复杂度为O(k)。即使在 best 情况下，图形实际上只是从源节点到目标节点的一条路径，第一个代码也将花费 O(1) + O(2) + O(3) + ... + 执行此 list(path) 调用的时间复杂度为 O(n²)。在这种“快乐路径”情况下，第二个版本将是 O(n)。当图中的分支因子变大时，事情只会变得更糟。

请备注您的代码

两个代码片段都有问题：

第一个版本没有针对运行ning 循环的保护。你应该添加一个访问标记，这样同一个节点就不会被访问两次
第二个版本好像有这样的保护，但是不够好。它检查下一个节点是否已经在队列中。但即使它不是，它以前也可能是，而且在那种情况下，它不应该被重新审视。我们可以使用 parent 来知道该节点是否已经被访问过。

下面是更正后的片段：

def bfs_1(graph, start, end):
    queue = []
    visited = set()
    queue.append([start])
    visited.add(start)
    while queue:
        path = queue.pop(0)
        node = path[-1]
        if node == end:
            return path
        for adjacent in graph.get(node, []):
            if adjacent not in visited:
                visited.add(adjacent)
                new_path = list(path)
                new_path.append(adjacent)
                queue.append(new_path)

和

def backtrace(parent, start, end):
    path = [end]
    while path[-1] != start:
        path.append(parent[path[-1]])
    path.reverse()
    return path
        

def bfs_2(graph, start, end):
    parent = {}
    queue = []
    queue.append(start)
    parent[start] = None
    while queue:
        node = queue.pop(0)
        if node == end:
            return backtrace(parent, start, end)
        for adjacent in graph.get(node, []):
            if adjacent not in parent:
                parent[adjacent] = node # <<<<< record its parent 
                queue.append(adjacent)

比较

我用下面的测试代码来测试上面的算法：

import random
from timeit import timeit

def create_graph(size):
    graph = {}
    nodes = list(range(size))
    for i in nodes:
        graph[i] = set(random.choices(nodes, k=3))
        if i in graph[i]:
            graph[i].remove(i)
        graph[i] = list(graph[i])
    return graph


graph = create_graph(40000)
print("version 1")
print(bfs_1(graph, 1, 2))
print("time used", timeit(lambda: bfs_1(graph, 1, 2), number=10))
print()
print("version 2")
print(bfs_2(graph, 1, 2))
print("time used", timeit(lambda: bfs_2(graph, 1, 2), number=10))

在 repl.it

上查看运行

生成的图有100 000个节点，分支因子约为2。边是随机的。大多数时候第二种算法比第一种算法快。当解决方案路径更长时，这种差异变得更加明显。

BFS寻找最短路径的两种实现方法，哪一种是明显的赢家？

Two implementation methods of BFS for finding the shortest path, which one is the obvious winner?

python

algorithm

breadth-first-search

time-complexity

space-complexity

请备注您的代码

比较