我们可以使用哪种算法来进行迷宫探索，广度优先搜索（BFS）还是深度优先搜索（DFS）？

Question

我知道我们可以使用DFS进行迷宫探索。但我认为我们也可以使用BFS进行迷宫探索。我有些困惑，因为我阅读过的大部分书籍和文章都使用DFS解决这个问题。 我的想法是，DFS的最佳情况时间复杂度会比BFS更好。但平均情况和最坏情况下，BFS和DFS的时间复杂度将是相同的，这就是为什么我们喜欢DFS而不是BFS的原因。 我的理解是正确的吗？

- Atinesh

---

深度优先搜索（DFS）可能更容易用于解决迷宫问题的可视化，但在性能方面，我认为两者应该是等效的。根据情况，一种方法比另一种方法更好。 - Abhishek Bansal

使用深度优先搜索，因为它更容易实现且解决方案的重构也很容易。 - Vikram Bhat

Answer 1

我很惊讶到目前为止没有人提到DFS和BFS给出结果的差异。

这两个算法的主要区别在于BFS返回最短路径，而DFS只返回一条路径。

因此，如果你想获得最短路径，请使用BFS，否则考虑其他优缺点（内存等）。

- pkacprzak

Answer 2

它们的运行时间相似，但是由于访问单元格的顺序不同，其中任何一个都可能在任何给定问题上表现得更好。

就空间使用而言，在trees方面，BFS平均会使用更多的内存，但对于更一般的图形，在某些情况下，它可以显著地使用更少的内存。

对于迷宫来说（如果我们将迷宫定义为从起点到达单元格只有一种方式而没有回溯的意思，这意味着它本质上是一棵树），BFS通常会使用更多的内存，因为我们需要同时在内存中保存多个路径，而DFS只需要跟踪任何给定时间的单个路径。

对于更一般的网格来说，在记住迄今为止访问过的单元格以防止重复访问单元格方面，哪种方法更好则不太明显。

如果您不关心内存，则可以选择任何一种。如果您对递归非常熟悉，则实现DFS应该更容易。

然而，如果你想要找到普通网格中某个给定单元格的最短路径，请使用BFS（或A*），因为它保证可以找到最短路径，而DFS则不行（在只有一条路径通向任何给定单元格的迷宫中仍可使用其中任意一种算法）。

- Bernhard Barker

---

对于一个复杂的迷宫，DFS平均上比BFS更节省内存。考虑一棵有m层的搜索树，每个父节点有b个子节点。最大内存使用量DFS为O(bm)，而BFS为O(b^m)。 - Chen Chen

Answer 3

两者应该是等效的。DFS被使用更多，因为它实现起来稍微容易一些。

- yasen

---

实现起来更简单？DFS 使用 stack，而 BFS 使用 queue。 - artur grzesiak

不是吗？我可以用4-5行代码编写迷宫的深度优先搜索算法，只需要一个条件和4个递归调用。对于广度优先搜索算法，我还需要另一个循环以及一些队列管理的代码行。 - yasen

@arturgrzesiak：基于栈的算法通常更容易实现，因为栈可以是隐式的（利用递归算法的调用栈），而不是显式的（需要创建队列的“包装器”函数和接收该队列作为按引用参数的“帮助器”函数）。因此，虽然这在名义上是一个栈/队列权衡，但编程语言通常更好地设置为处理DFS遍历而不是BFS。 - Drew Hall

BFS被使用得更加频繁，因为当存在多个解决方案时，它可以返回最短的解决方案，这通常是我们感兴趣的内容。DFS可能无法做到这一点。 - BlueRaja - Danny Pflughoeft

如果你知道出口就在附近，那么这种方法会更常用，这是一项完全不同的任务。否则，你应该以最简单的方式来实现它。此外，当涉及迷宫遍历时，深度优先搜索更自然——人类会以完全相同的方式行动。 - yasen

Answer 4

BFS占用太多内存，对于巨大的迷宫不是很好。

- gigir