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最短路徑

回答

相關問題