使用全局变量将全局变量递归到迭代

一个例子就是在这里我想保留的路径的跟踪深度优先搜索：

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()

我将如何做到这一点使用迭代和堆栈？

来源

2012-02-01 tskuzzy

有一个C＃示例，可以帮助您在这个链接：http://msdn.microsoft.com/en-us/library/bb513869.aspx – NoChance 2012-02-01 03:24:07

你知道如何做到这一点的一个函数，不使用全局变量？ – 2012-02-01 04:09:06

@ n.m。当然是。 – tskuzzy 2012-02-01 04:09:36

如果你可以扩展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

来源

2012-02-01 05:31:12 rio

使用全局变量将全局变量递归到迭代

回答

相关问题