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')