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

本文介绍了DFS在C ++中迷宫的最短路径的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我无法确定如何让这个工作...我试图找到使用DFS的目标的最短路径。我知道BFS是更好，但我被要求使用DFS为此。正如你可以看到，我试图做所有堆栈之间的比较，导致结束找到目标，但它不工作，只有第一个堆栈，导致目标是永远印刷...我知道某处我需要去访问节点，但我不知道究竟是如何。现在我得到一个目标的路径，但不是最短的。

I'm having trouble figuring out how exactly to get this to work... I'm attempting to get the shortest path to the goal using a DFS. I know that BFS is better but I was asked to use DFS for this. As you can see, I attempt to make a comparison between all stacks that lead to the end to find the goal, but it does not work, only the first stack that leads to the goal is ever printed... I know somewhere I need to unvisit nodes, but I cannot figure out exactly how. Right now I do get a path to the goal, but not the shortest one. Any help with this would be greatly appreciated.

推荐答案

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

Writing a non-recursive DFS is possible by using your own stack, but I find the recursive solution to be more elegant. Here is a sketch of one:

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