更改深度第一算法從遞歸到迭代

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)