C++中迷宫的DFS最短路径

我无法弄清楚如何才能正常工作......我试图通过DFS获得到目标的最短路径。我知道BFS更好，但我被要求使用DFS。正如你所看到的，我试图比较所有导致最终找到目标的堆栈，但它不起作用，只有导致目标的第一个堆栈被打印出来......我知道我需要的地方去观察节点，但我无法弄清楚究竟如何。现在我确实走到了目标的路径，但不是最短的路径。任何帮助，这将不胜感激。C++中迷宫的DFS最短路径

来源

2014-03-31 seanscal

任何具体的原因来编写**非递归** DFS？ –

@faranwath没有具体的原因，如果在这里递归会更容易，我完全支持它 – seanscal

图是如何定义的？ –

通过使用自己的堆栈来编写非递归DFS是可能的，但是我发现递归解决方案更加优雅。下面是一个草图：

DFS(vertex) 

    path.push_back(vertex) 
    visited[vertex] = true 

    if we found the exit 
     output path 
    else 
     for each neighbor v of vertex 
      if not visited[v] 
       DFS(v) 

    visited[vertex] = false 
    path.pop_back()

来源

2014-03-31 14:46:00

这帮助我完成了基于此模型的所有工作。非常感谢你，这使得它更有意义，并且比我试图编写的代码少很多。 – seanscal

一旦你获得递归版本的工作，编写非递归版本将是一个很好的练习。一个好处是你可以将栈溢出（不是双关），而且你可以更灵活地查看当前状态，或者如果你想对算法做一些修改。 –

C++中迷宫的DFS最短路径

回答

相关问题