鉴于此代码...
import Queue
def breadthFirstSearch(graph, start, end):
q = Queue.Queue()
path = [start]
q.put(path)
while not q.empty():
path = q.get()
lastNode = path[len(path) - 1]
if lastNode == end:
return path
for linkNode in graph[lastNode]:
if linkNode not in path:
newPath = []
newPath = path + [linkNode]
q.put(newPath)
其中graph是表示有向图的字典,eg, {'stack':['overflow'], 'foo':['bar']}
即stack指向overflow foo 指向 bar。
这个广度优先搜索能不能再优化一下?因为我打算在一个非常大的词典上使用它。
最佳答案
为什么不保留一组已访问的节点,这样您就不会一直访问相同的节点?这应该可行,因为它看起来不像您使用的是加权图。像这样:
import Queue
def bfs(graph, start, end):
q = Queue.Queue()
path = [start]
q.put(path)
visited = set([start])
while not q.empty():
path = q.get()
last_node = path[-1]
if last_node == end:
return path
for node in graph[last_node]:
if node not in visited:
visited.add(node)
q.put(path + [node])
关于Python广度优先搜索优化,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16747125/