如何跟踪广度优先搜索的路径,例如以下示例:
如果搜索键 11
,则返回连接 1 到 11 的 最短 列表。
[1, 4, 7, 11]
最佳答案
你应该看看 http://en.wikipedia.org/wiki/Breadth-first_search首先。
下面是一个快速实现,其中我使用列表列表来表示路径队列。
# graph is in adjacent list representation
graph = {
'1': ['2', '3', '4'],
'2': ['5', '6'],
'5': ['9', '10'],
'4': ['7', '8'],
'7': ['11', '12']
}
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, '1', '11')
这会打印:['1', '4', '7', '11']
另一种方法是维护从每个节点到其父节点的映射,并在检查相邻节点时记录其父节点。搜索完成后,只需根据父映射进行回溯即可。
graph = {
'1': ['2', '3', '4'],
'2': ['5', '6'],
'5': ['9', '10'],
'4': ['7', '8'],
'7': ['11', '12']
}
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, '1', '11')
以上代码基于没有循环的假设。
关于python - 如何在广度优先搜索中追踪路径?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8922060/