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

Question

我正在尝试找出一种方法，使用某种形式的循环将函数 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

Answer 1

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

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)

作为旁注，您的代码正在使用访问列表，这将使事情O(n^2)变慢，您可以使用集合 相反。此外，如果您在搜索中只需要进行存在/缺席检查，那么您可以在找到目标后立即退出。