Python DFS和BFS

Question

这里http://www.python.org/doc/essays/graphs/是DFS吗？

我尝试用'兄弟姐妹'做点什么,但它不起作用.任何人都可以写BFS类似于该网站的代码.

Answer 1

是的,它是DFS.

要编写BFS,您只需要保留"todo"队列.您可能还希望将该函数转换为生成器,因为通常在生成所有可能的路径之前故意结束BFS.因此,此函数可用于find_path或find_all_paths.

def paths(graph, start, end):
    todo = [[start, [start]]]
    while 0 < len(todo):
        (node, path) = todo.pop(0)
        for next_node in graph[node]:
            if next_node in path:
                continue
            elif next_node == end:
                yield path + [next_node]
            else:
                todo.append([next_node, path + [next_node]])

以及如何使用它的示例:

graph = {'A': ['B', 'C'],
         'B': ['C', 'D'],
         'C': ['D'],
         'D': ['C'],
         'E': ['F'],
         'F': ['C']}

for path in paths(graph, 'A', 'D'):
    print path