我有一个带有起点和终点的开放迷宫。我写了一个 BFS 和一个 DFS 搜索算法来解决这个迷宫。我的 BFS 找到了最短的解决方案，但我的 DFS（向下、向左、向上、向右）创建了一个锯齿形作为解决方案。这个对吗？DFS 在开放的迷宫中应该如何表现？
编辑： http ://postimg.org/image/n049oua8n/这是路径，从 P 开始。端点在底部，但中间路径对我来说看起来不对 =/ 我认为算法正在跳过一列，正确的？它应该完全填满中间部分吗？
问问题
1063 次
2 回答
2
是的，它是正确的，因为 DFS 深入探索了图形（并且没有找到最短路径）。给定访问源s，DFS 访问其邻居u之一，然后u深入访问其邻居之一。当访问给定节点的所有邻居时，访问父节点的另一个邻居，依此类推。
而 BFS，考虑到访问的来源，s首先访问它的所有邻居，然后开始深化。
于 2013-09-26T19:18:01.323 回答
1
这听起来是正确的：DFS 将在第一个方向（向下）尽可能深入迷宫，当它无法继续前进时，它将返回到最后一个十字路口并向左走，然后再次向下。
有一种名为“flood fill”的绘画算法，它通过对像素进行 DFS 或 BFS 来填充空间。它的工作动画很好地展示了两种图搜索算法之间的差异。
这是一个 BFS 的食物填充，你可以看到它在各个方向搜索空间：
这是使用 DFS 进行的洪水填充，您可以看到它首先在一个方向上搜索空间，然后回溯以填充孔：
于 2013-09-26T19:05:22.290 回答