如何避免使用生成器的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