使用深度优先搜索算法解决迷宫-Java 学习之路

所以我有这个学校项目：我作为输入一个迷宫，我必须解决它 . 我想过使用DFS算法来做到这一点 .

到目前为止我所做的是将我的迷宫变成一个图形，其中顶点是迷宫的非墙壁位置 .

我在网上找到了DFS的一些伪代码 . 我实现了它，但我不明白我应该如何摆脱它 . 算法的伪代码是：

dfs(graph G,vertex a)
   {
      ColorNode(a);
      for all vertices e adjacent to a
      {
        if e is endpoint
         END
        if e is not colored
         dfs(G, e)
      }  
    }

有了这个算法，所有的节点最终都被着色了 . 如果有人能帮我一把，那就太好了！

3 回答

3

路径由堆栈跟踪中的节点组成 . 您可以修改dfs以返回bool，如果它找到了结尾，并且当它返回true时，您将打印或添加到列表顶点 a （请注意，这会向后提供路径） .

或者有一个堆栈（全局，或在您的函数中传递对它的引用） . 当你调用dfs push vertex a到它并在你回来时弹出它 . 然后，当您到达 endpoints 时，堆栈包含路径 .

除非END停止整个程序，否则所有可到达的节点都应该变为彩色 . 我怀疑你写了它，以便你在找到目的地之后继续前进，这样你的程序就会保持着色节点 . 没有很好的方法来结束递归（你可以抛出一个异常，但这只是糟糕的风格）所以你需要让调用者知道找到了解决方案并停止尝试其他事情（如果找到解决方案，你可以返回一个bool ，所以当一个调用返回true时，你可以立即返回true） .

回复于 2024-05-05T22:30:48+08:00
0

如果所有节点最终都是彩色的，那么在图形构造或迷宫设计中一定是错误的，因为使用此代码迟早会找到退出 .

关于找回路径，您可以这样做：当您打开一个新节点时，向该节点传递对您来自的节点的引用，并将其存储在节点内：当您到达 endpoints 时，只需按照指针向后移动存储，您可以重建带您到那里的路径 .

回复于 2024-05-05T22:30:48+08:00
1
这些问题“我该如何做DFS？”问题是，对真实情况的了解很少 .

一旦你问自己我将如何旅行迷宫找到它的出口？是（好......应该）或多或少直截了当，该做什么：

您可以将线程编织到起始位置，然后按照以下简单规则开始思考：
- 每当你到达一个路口时，你会检查是否还有一些你以前没有去过的地方，如果有的话，那么你只需沿那个方向前进 .
- 如果您到达一个不再可能继续前进的交叉路口，您可以通过穿过迷宫地板上的两个分支将该位置标记为被访问 . 下次你将跳过这个路口，然后你从你来自的地方回去 .
就您的代码片段而言：
```
dfs(graph G,vertex a)//What should I do at this junction?
   {
      ColorNode(a);//Stretch your thread to that junction
      for all vertices e adjacent to a//Choose a direction you haven't visited yet
      {
        if e is endpoint//If I found the exit of the maze
         END//I survived
        if e is not colored//If I haven't been in this direction earlier
         dfs(G, e)//Let's move on to that direction
      }  
    }
```
回复于 2024-05-05T22:30:48+08:00

使用深度优先搜索算法解决迷宫

3 回答

相关问题