我有一个脚本,它使用邻接图和 BFS 算法来查找两点之间的路径。该图有大约 10,000 个顶点,脚本设置如下:
graph = {...
'9660': ['9661', '9662', '9659'],
'9661': ['9654', '9660'],
'9662': ['9660', '9663'],
'9663': ['9664', '9662'],
'9664': ['9665', '9663'],
...}
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, '50', '8659')
因为这个算法适用于小的邻接图,我猜 python 只需要很长时间来处理这个大小的图。我的目标是找到最短路径,但如果我什至找不到一条路径,那目前是不可能的。是否有使用大型邻接图处理路径查找的 python 解决方案?如果是这样,我可以举个例子吗?
最佳答案
您没有跟踪访问过的节点,如果您的图不是有向无环图,这可能会导致大量时间浪费。例如,如果您的图表是
{'A': ['B', 'C', 'D', 'E'],
'B': ['A', 'C', 'D'],
'C': ['A', 'B', 'D'],
'D': ['A', 'B', 'C'],
'E': ['F'],
'F': ['G'],
'G': ['H'],
...
'W': ['X'],
'X': ['Y'],
'Y': ['Z']}
使用您的算法调用 bfs(graph, 'A', 'Z')
会在最终到达 Z 之前不必要地循环“A”、“B”、“C”和“D”。而如果您跟踪访问过的节点,则只需将“A”、“B”、“C”和“D”的邻居添加到队列中一次。
def bfs(graph, start, end):
# maintain a queue of paths
queue = []
# push the first path into the queue
queue.append([start])
# already visited nodes
visited = set()
while queue:
# get the first path from the queue
path = queue.pop(0)
# get the last node from the path
node = path[-1]
# if node has already been visited
if node in visited:
continue
# path found
if node == end:
return path
# enumerate all adjacent nodes, construct a new path and push it into the queue
else:
for adjacent in graph.get(node, []):
# add the path only if it's end node hasn't already been visited
if adjacent not in visited
new_path = list(path)
new_path.append(adjacent)
queue.append(new_path)
# add node to visited set
visited.add(node)
使用这个版本的算法和字母图,队列和访问集在整个算法的 while 循环顶部看起来像这样:
queue = [ ['A'] ]
visited = {}
queue = [ ['A', 'B'], ['A', 'C'], ['A', 'D'], ['A', 'E'] ]
visited = {'A'}
queue = [ ['A', 'C'], ['A', 'D'], ['A', 'E'], ['A', 'B', 'C'],
['A', 'B', 'D'] ]
visited = {'A', 'B'}
queue = [ ['A', 'D'], ['A', 'E'], ['A', 'B', 'C'], ['A', 'B', 'D'],
['A', 'C', 'D'] ]
visited = {'A', 'B', 'C'}
queue = [ ['A', 'E'], ['A', 'B', 'C'], ['A', 'B', 'D'], ['A', 'C', 'D'] ]
visited = {'A', 'B', 'C', 'D'}
queue = [ ['A', 'B', 'C'], ['A', 'B', 'D'], ['A', 'C', 'D'], ['A', 'E', 'F'] ]
visited = {'A', 'B', 'C', 'D', 'E'}
queue = [ ['A', 'B', 'D'], ['A', 'C', 'D'], ['A', 'E', 'F'] ]
visited = {'A', 'B', 'C', 'D', 'E'}
queue = [ ['A', 'C', 'D'], ['A', 'E', 'F'] ]
visited = {'A', 'B', 'C', 'D', 'E'}
queue = [ ['A', 'E', 'F'] ]
visited = {'A', 'B', 'C', 'D', 'E'}
queue = [ ['A', 'E', 'F', 'G'] ]
visited = {'A', 'B', 'C', 'D', 'E', 'F'}
queue = [ ['A', 'E', 'F', 'G', 'H'] ]
visited = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}
...
...
queue = [ ['A', 'E', 'F', 'G', 'H', ..., 'X', 'Y', 'Z'] ]
visited = {'A', 'B', 'C', 'D', 'E', 'F', 'G', ..., 'X', 'Y'}
# at this point the algorithm will pop off the path,
# see that it reaches the goal, and return
这比添加像 ['A', 'B', 'A', 'B', 'A', 'B', ...]
这样的工作要少得多。
关于Python 在寻路时卡住,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13663710/