Python DFS和BFS

Question

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

我试图用“兄弟姐妹”做某件事，但它不起作用。 任何人都可以编写类似于本网站代码的BFS。

Answer 1

你为什么不检查一个体面的图形实现像python-graph？

http://code.google.com/p/python-graph/

Answer 2

是的，这是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 

Answer 3

下面是一个O（N *最大（顶点度））广度优先搜索的实现。 bfs函数以广度优先的顺序生成节点，并为每个节点生成一个可用于追溯最短路径返回起点的生成器。路径的懒惰特性意味着您可以遍历生成的节点来查找感兴趣的点，而无需花费构建所有中间路径的代价。

import collections 

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

def build_path(node, previous_map): 
    while node: 
     yield node 
     node = previous_map.get(node) 

def bfs(start, graph): 
    previous_map = {} 
    todo = collections.deque() 
    todo.append(start) 
    while todo: 
     node = todo.popleft() 
     yield node, build_path(node, previous) 
     for next_node in graph.get(node, []): 
      if next_node not in previous_map: 
       previous_map[next_node] = node 
       todo.append(next_node) 

for node, path in bfs('A', GRAPH): 
    print node, list(path) 

Answer 4

def recursive_dfs(graph, start, path=[]): 
    '''recursive depth first search from start''' 
    path=path+[start] 
    for node in graph[start]: 
    if not node in path: 
     path=recursive_dfs(graph, node, path) 
    return path 

def iterative_dfs(graph, start, path=[]): 
    '''iterative depth first search from start''' 
    q=[start] 
    while q: 
    v=q.pop(0) 
    if v not in path: 
     path=path+[v] 
     q=graph[v]+q 
    return path 

def iterative_bfs(graph, start, path=[]): 
    '''iterative breadth first search from start''' 
    q=[start] 
    while q: 
    v=q.pop(0) 
    if not v in path: 
     path=path+[v] 
     q=q+graph[v] 
    return path 

''' 
    +---- A 
    | / \ 
    | B--D--C 
    | \ |/
    +---- E 
''' 
graph = {'A':['B','C'],'B':['D','E'],'C':['D','E'],'D':['E'],'E':['A']} 
print 'recursive dfs ', recursive_dfs(graph, 'A') 
print 'iterative dfs ', iterative_dfs(graph, 'A') 
print 'iterative bfs ', iterative_bfs(graph, 'A')