为什么深度优先搜索被认为是节省空间的？

Question

在我正在学习的一门算法课程中，据说深度优先搜索（DFS）比广度优先搜索（BFS）更节省空间。

为什么呢？

虽然它们基本上都在做相同的事情，但在DFS中，我们正在堆叠当前节点的后续节点，而在BFS中，我们正在将后续节点排队。

Answer 1

在DFS中，使用的空间是O（h），其中h是树的高度。

在BFS中，使用的空间是O（w），其中w是树的“宽度”。

在典型的二叉树（即随机二叉树）中，w=ω（n）和h=O（sqrt（n））。

在平衡树中，w=Omega（n）和h=O（log n）。

Answer 2

在DFS中，完全平衡树上的线性深度O（log（n））只需要空间，而BFS（宽度优先搜索）需要O（n）（树的最宽部分是二叉树中n/2个节点的最低深度）。

例子：

               1
              / \  
             /   \  
            /     \ 
           /       \
          /         \  
         /           \  
        /             \ 
       /               \
       2               2 
      / \             / \ 
     /   \           /   \  
    /     \         /     \  
   /       \       /       \  
   3       3       3       3
  / \     / \     / \     / \ 
 /   \   /   \   /   \   /   \  
 4   4   4   4   4   4   4   4
/ \ / \ / \ / \ / \ / \ / \ / \ 
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 

DFS需要空间：4
BFS需要在最后第二行空间8

如果分支因子越高，情况就会变得更糟

Answer 3

您的困惑源于这样一个事实，即您显然认为DFS算法可以通过用后进先出堆栈替换FIFO队列从BFS算法获得。

这是一个普遍的误解——这根本不是真的。经典的DFS算法不能通过用堆栈替换BFS队列来获得。这些算法之间的差异要显著得多。

如果您采用BFS算法，并简单地用后进先出堆栈替换FIFO队列，您将获得可以称为伪DFS算法的东西。这种伪DFS算法确实可以正确地再现DFS顶点前向遍历序列，但它不具有DFS空间效率，并且不支持DFS后向遍历（回溯）。

同时，通过这种简单的队列到堆栈替换，无法从BFS获得真正的经典DFS。经典的DFS是一种完全不同的算法，具有显著不同的核心结构。True DFS是一种真正的递归算法，它使用堆栈进行回溯，而不是存储顶点发现“前端”（如BFS中的情况）。最直接的结果是，在DFS算法中，最大堆栈深度等于DFS遍历中距原点顶点的最大距离。在BFS算法中（如前面提到的伪DFS），最大队列大小等于最大顶点发现前沿的宽度。

说明DFS和BFS（以及伪DFS）之间内存消耗峰值差异的最突出和最极端的例子是星图：一个由大量外围顶点包围的单个中心顶点（例如，1000）外围顶点通过边缘连接到中心顶点。如果在此图上使用中心顶点作为原点运行BFS，队列大小将立即跳转到1000。如果使用伪DFS（即简单地用堆栈替换队列），显然会发生同样的事情。但是经典的DFS算法只需要1（！）遍历整个图表。看出区别了吗？1000对1。这就是DFS更好的空间效率的含义。

基本上，阅读任何一本关于算法的书，找到经典DFS的描述，看看它是如何工作的。您会注意到，BFS和DFS之间的区别远远大于队列与堆栈之间的区别。

另外，还应该说，我们可以构建一个图的示例，该图在BFS下具有较小的峰值内存消耗。因此，关于DFS更好的空间效率的声明应该被视为可以“平均”应用于某些隐含的“nice”图类。