Python DFS и BFS - PullRequest
Новая
       51

Python DFS и BFS

4 голосов
/ 20 марта 2011

Здесь http://www.python.org/doc/essays/graphs/ верно ли DFS?

Я пытаюсь что-то сделать с «братьями и сестрами», но это не работает. Может кто-нибудь написать BFS, похожий на код с этого сайта.

Ответы [ 3 ]

8 голосов
/ 20 марта 2011

Да, это 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
1 голос
/ 20 марта 2011

Вот реализация поиска в ширину O (N * max (степень вершины)).Функция 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)
0 голосов
/ 15 сентября 2017 
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')
...