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

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)