6

鉴于此代码...

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是表示有向图的字典,例如,{'stack':['overflow'], 'foo':['bar']}stack指向overflow,foo指向bar。

这种广度优先搜索能否进一步优化?因为我打算在一本非常大的字典上使用它。

4

1 回答 1

10

为什么不保留一组访问过的节点,这样您就不会一直碰到相同的节点?这应该有效,因为它看起来不像您使用的是加权图。像这样的东西:

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])
于 2013-05-25T07:00:24.443 回答