在什么意义上 DFS 比 BFS 快？

Question

在阅读有关 DFS 与 BFS 的文章时，我发现 DFS 比 BFS 更快，并且需要更少的内存。

我的实现都是用 C++ 实现的，为 DFS 制作一个堆栈，为 BFS 制作一个队列。有人可以解释一下，速度和内存要求有何不同？

Answer 1

• 内存要求：堆栈大小受深度限制，而队列大小受宽度限制。对于具有 n 个节点的平衡二叉树，这意味着堆栈大小将为 log(n)，但队列大小将为 b O(n)。请注意，在所有情况下，BFS 可能都不需要显式队列——例如，在嵌入数组的二叉树中，应该可以计算下一个索引。

• 速度：我不认为那是真的。对于完整搜索，这两种情况都会访问所有节点，而不会产生显着的额外开销。如果在找到匹配元素时可以中止搜索，如果搜索元素在搜索树中通常位于更高的位置，那么 BFS 通常应该更快，因为它逐级进行。如果搜索的元素通常相对较深并且找到多个元素中的一个就足够了，则 DFS 可能会更快。