在我参加的一门算法类(class)中，据说深度优先搜索 (DFS) 的空间效率远高于广度优先搜索 (BFS)。
这是为什么呢？
虽然它们基本上做同样的事情，但在 DFS 中，我们将当前节点的后继者堆叠起来，而在 BFS 中，我们将后继者加入队列。
最佳答案
您的困惑源于您显然假设 DFS 算法可以通过用 LIFO 堆栈替换 FIFO 队列从 BFS 算法中获得。
这是一个普遍的误解 - 它根本不是真的。经典的DFS算法不能用栈代替BFS队列得到。这些算法之间的差异更为显着。
如果您采用 BFS 算法并简单地将 FIFO 队列替换为 LIFO 堆栈，您将获得可以称为 pseudo-DFS 算法的东西。这种伪DFS算法确实会正确再现DFS顶点前向遍历序列，但不具备DFS空间效率，也不支持DFS后向遍历(回溯)。
与此同时，真正的经典 DFS 无法通过这种简单的队列到堆栈替换从 BFS 获得。经典的 DFS 是一种完全不同的算法，具有明显不同的核心结构。真正的 DFS 是一种真正的递归算法，它使用堆栈进行回溯，而不是用于存储“前面”的顶点发现(如 BFS 中的情况)。最直接的结果是，在 DFS 算法中，最大堆栈深度等于 DFS 遍历中距原点的最大距离。在 BFS 算法中(如在上述伪 DFS 中)，最大队列大小等于最大顶点发现前沿的宽度。
说明 DFS 和 BFS(以及伪 DFS)之间峰值内存消耗差异的最突出和极端的例子是星图:一个由大量数字包围的单个中心顶点(例如， 1000) 的外围顶点，每个外围顶点通过一条边连接到中心顶点。如果您使用中心顶点作为原点在此图上运行 BFS，队列大小将立即跳到 1000。如果您使用伪 DFS(即，如果您只是用堆栈替换队列)，显然会发生同样的事情。但是经典的 DFS 算法只需要 1 (!) 的堆栈深度来遍历整个图。看到不同？ 1000 与 1。这就是DFS更好的空间效率的意思。
基本上，阅读任何有关算法的书籍，找到对经典 DFS 的描述，看看它是如何工作的。您会注意到 BFS 和 DFS 之间的区别远比单纯的队列与堆栈的区别大得多。
附言还应该说，可以构建一个在 BFS 下峰值内存消耗较小的图形示例。因此，关于 DFS 更好的空间效率的陈述应该被视为可能“平均”应用于某些隐含的“好”图类。
关于algorithm - 为什么深度优先搜索声称具有空间效率？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20429310/