Python 深度优先搜索和广度优先搜索

Question

这里有个链接 http://www.python.org/doc/essays/graphs/ 是在讲深度优先搜索（DFS），对吧？

我想用“兄弟节点”做点什么，但没成功。有没有人能写个广度优先搜索（BFS）的代码，跟这个网站上的代码类似？

Answer 1

在编程中，有时候我们需要把一些数据存储起来，以便后续使用。这个过程就像把东西放进一个盒子里，等需要的时候再拿出来。我们可以使用不同的方式来存储这些数据，比如使用变量、数组或者数据库等。

变量就像是一个小盒子，我们可以给它一个名字，然后把数据放进去。比如，我们可以有一个叫做“年龄”的变量，里面存放着一个数字，表示我们的年龄。

数组则是一个可以存放多个数据的盒子，想象一下这是一个可以放很多小盒子的盒子。比如，我们可以用一个数组来存放一周七天的名字。

数据库则是一个更大的存储空间，可以存放大量的数据，并且可以很方便地进行查询和管理。就像一个图书馆，里面有很多书，我们可以通过书名或者作者来找到我们想要的书。

总之，存储数据的方式有很多，选择合适的方法可以让我们的程序更高效、更易于管理。

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

Answer 2

这里有一个时间复杂度为 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 3

是的，这个是深度优先搜索（DFS）。

如果你想写广度优先搜索（BFS），你只需要保持一个“待办”队列。你可能还想把这个函数变成一个生成器，因为广度优先搜索通常会在生成所有可能路径之前就故意结束。所以这个函数可以用来找路径或者找所有路径。

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