python - Python DFS 和 BFS

Question

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

我尝试对“兄弟姐妹”做一些事情，但它不起作用。任何人都可以编写类似于此站点代码的 BFS。

Answer 1

Yes, it is DFS.

To write a BFS you just need to keep a "todo" queue. You probably also want to turn the function into a generator because often a BFS is deliberately ended before it generates all possible paths. Thus this function can be used to be find_path or 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]])

And an example of how to use it:

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 2

这是一个 O(N * max(vertex degree)) 广度优先搜索实现。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 3

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