使用全局變量將全局變量遞歸到迭代

Question

如何將使用全局變量的遞歸函數翻譯爲迭代變量？這

一個例子就是在這裏我想保留的路徑的跟蹤深度優先搜索：

path = [] 

function dfs(node) 
    node.visited = true 
    path.append(node) 

    if node == goal 
     print path 
     stop; 

    for child in node.children 
     if !child.visited 
      dfs(child) 

    path.pop() 

我將如何做到這一點使用迭代和堆棧？

Answer 1

如果你可以擴展Node類，它將如下所示。

function iterative_dfs(start_node) 
    start_node.next = null 
    start_node.visited = true 

    stack = [] 
    stack.push(start_node) 

    while !stack.empty? 
     node = stack.pop 

     if node == goal 
      path = [] 
      while node 
       path.push(node) 
       node = node.next 
      path.reverse 
      print path 
      stop; 

     for child in node.children 
      if !child.visited 
       child.next = node 
       child.visited = true 
       stack.push(child) 

此外，您的代碼有一個錯誤。如果找不到目標，應該彈出節點。

function dfs(node) 
    node.visited = true 
    path.append(node) 

    if node == goal 
     print path 
     stop; 

    for child in node.children 
     if !child.visited 
      dfs(child) 

    path.pop # You need this