如何在广度优先搜索中跟踪路径？
如何在广度优先搜索中跟踪路径？
提问于 2012-01-19 14:45:18
在下面的示例中，如何跟踪广度优先搜索的路径：
如果搜索关键字
，则返回
最短
连接1到11的列表。
[1, 4, 7, 11]回答 5
Stack Overflow用户
发布于 2018-05-29 11:37:24
非常简单的代码。每次发现节点时，您都会一直附加路径。
graph = {
'A': set(['B', 'C']),
'B': set(['A', 'D', 'E']),
'C': set(['A', 'F']),
'D': set(['B']),
'E': set(['B', 'F']),
'F': set(['C', 'E'])
}
def retunShortestPath(graph, start, end):
queue = [(start,[start])]
visited = set()
while queue:
vertex, path = queue.pop(0)
visited.add(vertex)
for node in graph[vertex]:
if node == end:
return path + [end]
else:
if node not in visited:
visited.add(node)
queue.append((node, path + [node]))Stack Overflow用户
发布于 2014-08-30 23:26:26
我非常喜欢乔的第一个答案！这里唯一缺少的是将顶点标记为已访问。
为什么我们需要这样做？
假设有另一个节点编号13与节点11相连，现在我们的目标是找到节点13。
运行一小段时间后，队列将如下所示：
[[1, 2, 6], [1, 3, 10], [1, 4, 7], [1, 4, 8], [1, 2, 5, 9], [1, 2, 5, 10]]请注意，末尾有两条节点编号为10的路径。
这意味着来自节点编号10的路径将被检查两次。在这种情况下，它看起来并不是很糟糕，因为节点编号10没有任何子节点。但它可能真的很糟糕(即使在这里，我们也会无缘无故地检查该节点两次。)
节点编号13不在这些路径中，所以程序在到达end..And中节点编号为10的第二个路径之前不会返回，我们将重新检查它。
我们所缺少的是一组标记被访问的节点并不再检查它们的集合。
修改后的代码如下：
graph = {
1: [2, 3, 4],
2: [5, 6],
3: [10],
4: [7, 8],
5: [9, 10],
7: [11, 12],
11: [13]
}
def bfs(graph_to_search, start, end):
queue = [[start]]
visited = set()
while queue:
# Gets the first path in the queue
path = queue.pop(0)
# Gets the last node in the path
vertex = path[-1]
# Checks if we got to the end
if vertex == end:
return path
# We check if the current node is already in the visited nodes set in order not to recheck it
elif vertex not in visited:
# enumerate all adjacent nodes, construct a new path and push it into the queue
for current_neighbour in graph_to_search.get(vertex, []):
new_path = list(path)
new_path.append(current_neighbour)
queue.append(new_path)
# Mark the vertex as visited
visited.add(vertex)
print bfs(graph, 1, 13)程序的输出将是：
[1, 4, 7, 11, 13]如果没有不必要的复查..
Stack Overflow用户
发布于 2012-01-19 16:32:41
我想我应该试着把这段代码写得很有趣：
graph = {
'1': ['2', '3', '4'],
'2': ['5', '6'],
'5': ['9', '10'],
'4': ['7', '8'],
'7': ['11', '12']
}
def bfs(graph, forefront, end):
# assumes no cycles
next_forefront = [(node, path + ',' + node) for i, path in forefront if i in graph for node in graph[i]]
for node,path in next_forefront:
if node==end:
return path
else:
return bfs(graph,next_forefront,end)
print bfs(graph,[('1','1')],'11')
# >>>
# 1, 4, 7, 11如果你想要循环，你可以添加这个：
for i, j in for_front: # allow cycles, add this code
if i in graph:
del graph[i]页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/8922060
复制相关文章
相似问题