更改深度第一算法从递归到迭代

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)

作为旁注，您的代码正在使用visited的列表，这将使 O(n^2)慢速，您可以使用set。另外，如果您需要从搜索中所需的全部检查/不存在检查，则可以立即退出目标。

Answer 2

您将首先需要一个深度的堆栈（或首先是宽度的队列）。

def helper(graph, start, visited):
    stack = [ start ]
    while len(stack) > 0:
        current = stack.pop()
        if current in graph:
            for neighbor in graph[current]:
                if neighbor not in visited:
                    visited.append( neighbor )
                    stack.append(neighbor)