Как избежать максимальной глубины рекурсии в python с генераторами?

Question

Я нахожу кратчайший путь с помощью BFS, я получаю это RecursionError: maximum recursion depth exceeded in comparison очень быстро, любое предложение о том, как избежать его с помощью генераторов? Или сделать его итеративным является единственным хорошим вариантом?

код ниже:

def bfs_paths(graph, start, goal): 
    queue = [(start, [start])] 
    while queue: 
     (vertex, path) = queue.pop(0) 
     for next in graph[vertex] - set(path): 
      if next == goal: 
       yield path + [next] 
      else: 
       queue.append((next, path + [next])) 

def shortest_path(graph, start, goal): 
    try: 
     return next(bfs_paths(graph, start, goal)) 
    except StopIteration: 
     return None 

Пример использования:

graph = {'A': set(['B', 'C']), 
     'B': set(['A', 'D', 'E']), 
     'C': set(['A', 'F']), 
     'D': set(['B']), 
     'E': set(['B', 'F']), 
     'F': set(['C', 'E'])} 

shortest_path(graph, 'A', 'F') # ['A', 'C', 'F'] 

Answer 1

Попробуйте это. Он включает посещенный набор. Я также изменил имя переменной «next» на «node», поскольку это встроенная функция

def bfs_paths(graph, start, goal): 
    visited = set() 
    queue = [(start, [start])] 
    while queue: 
     vertex, path = queue.pop(0) 
     visited.add(vertex) 
     for node in graph[vertex]: 
      if node in visited: 
       continue 
      elif node == goal: 
       yield path + [node] 
      else: 
       queue.append((node, path + [node])) 

def shortest_path(graph, start, goal): 
    try: 
     return next(bfs_paths(graph, start, goal)) 
    except StopIteration: 
     return None