本文介绍了Python中的BFS算法的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
graph={ 0:[1,3,4], 1:[0,2,4], 2:[1,6], 3:[0,4,6], 4:[0,1,3,5], 5:[4], 6:[2,3] }
def bfs(graph, start, path=[]):
queue = [start]
while queue:
vertex = queue.pop(0)
if vertex not in path:
path.append(vertex)
queue.extend(graph[vertex] - path)
return path
print bfs(graph, 0)
你们好!有人可以帮我这个BFS代码吗?我不明白如何解决此队列行。
Guys! Can someone help me with this bfs code? I can't understand how to solve this queue line.
推荐答案
将队列扩展为路径上尚未出现的所有节点,请使用设置操作:
To extend your queue with all nodes not yet seen on the path, use set operations:
queue.extend(set(graph[vertex]).difference(path))
或使用生成器表达式:
queue.extend(node for node in graph[vertex] if node not in path)
列表不支持减法。
您并不需要 来过滤节点,但是,您的代码可以使用简单:
You don't really need to filter the nodes, however, your code would work with a simple:
queue.extend(graph[vertex])
,因为如果顶点不在路径中:
测试还可以防止重新访问节点。
as the if vertex not in path:
test also guards against re-visiting nodes.
您不应使用列表作为默认参数,请参见;您根本不需要默认参数:
You should not use a list as default argument, see "Least Astonishment" and the Mutable Default Argument; you don't need a default argument here at all:
def bfs(graph, start):
path = []
演示:
>>> graph={ 0:[1,3,4], 1:[0,2,4], 2:[1,6], 3:[0,4,6], 4:[0,1,3,5], 5:[4], 6:[2,3] }
>>> def bfs(graph, start):
... path = []
... queue = [start]
... while queue:
... vertex = queue.pop(0)
... if vertex not in path:
... path.append(vertex)
... queue.extend(graph[vertex])
... return path
...
>>> print bfs(graph, 0)
[0, 1, 3, 4, 2, 6, 5]
这篇关于Python中的BFS算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!