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

如何使用生成器避免 python 中的最大递归深度？

How to avoid maximum recursion depth in python with generators?

python

recursion

generator

breadth-first-search