python - 将深度优先算法从递归更改为迭代

我试图找出一种使用某种形式的循环将函数helper从递归转换为迭代的方法。

我现在真的很沮丧，我想知道你们中的任何一个都可以提供帮助。这是一个使用深度优先遍历来搜索给定起点和终点路径是否存在于有向图中的函数。

def helper(graph, current, visited):
    if current in graph:
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.append( neighbor )
                helper(graph, neighbor, visited)

def DFS(graph, start, goal):
    if start not in graph and goal not in graph:
        return False
    visited = [start]
    helper(graph, start, visited)
    return goal in visited

最佳答案

解决方案是使用显式堆栈：

stack = [start]
while len(stack) > 0:
    node = stack.pop()
    for x in graph[node]:
        if x not in visited:
            visited.add(x)
            stack.append(x)

附带说明一下，您的代码正在使用visited的列表，这会使O(n^2)变慢，您可以改用set。如果您只需要搜索搜索是否存在，您也可以在找到目标后立即退出。

关于python - 将深度优先算法从递归更改为迭代，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/40963247/