在一个算法，我当然要带，它说，深度优先搜索（DFS）比广度优先搜索（BFS）更有效利用空间。

In an algorithms course I'm taking, it's said that Depth-First Search (DFS) is far more space efficient than Breadth-First Search (BFS).

这是为什么？虽然他们基本上都是做同样的事情，在DFS我们堆叠当前节点的接班人，而在BFS我们将排入队列接班人。

Why is that? Although they are basically doing the same thing, in DFS we're stacking the current node's successors while in BFS we're enqueueing the successors.

推荐答案

您混淆的事实而产生，你显然认为DFS算法可以从BFS算法用一个后进先出栈更换FIFO队列中获得。

Your confusion is stemming from the fact that you apparently assume that DFS algorithm can be obtained from BFS algorithm by replacing the FIFO queue with a LIFO stack.

这是一个普遍的误解 - 这是不正确的。经典的DFS算法无法通过用栈取代BFS队列来获得。这些算法之间的差异是更显著。

This is a popular misconception - it is simply not true. The classic DFS algorithm cannot be obtained by replacing the BFS queue with a stack. The difference between these algorithms is much more significant.

如果你把一个BFS算法只需更换一个后进先出堆栈的FIFO队列，你会得到的东西，可以被称为的伪DFS 的算法。此伪DFS算法将确实正确地重现的DFS顶点向前遍历序列，但它将不具有DFS空间利用率和它不支持的DFS向后遍历（回溯）。

If you take a BFS algorithm and simply replace the FIFO queue with a LIFO stack, you will obtain something that can be called a pseudo-DFS algorithm. This pseudo-DFS algorithm will indeed correctly reproduce the DFS vertex forward traversal sequence, but it will not have DFS space efficiency and it will not support DFS backward traversal (backtracking).

同时，真正的经典的DFS不能从BFS由这种幼稚队列与堆的置换得到。经典的DFS是一个完全不同的算法有显著不同的核心结构。真正的DFS是一个真正的递归的算法，使用堆栈的回溯的目的，不用于存储顶点发现前线（如在BFS的情况下）。的，最直接的结果是，在DFS算法的最大堆栈深度等于从在DFS遍历原点顶点的最大距离。在BFS算法（如在前述伪DFS）的最大队列长度等于最大顶点发现前面的宽度。

Meanwhile, the true classic DFS cannot be obtained from BFS by such a naive queue-to-stack replacement. The classic DFS is a completely different algorithm with significantly different core structure. True DFS is a genuinely recursive algorithm that uses stack for backtracking purposes, not for storing the vertex discovery "front" (as is the case in BFS). The most immediate consequence of that is that in DFS algorithm the maximum stack depth is equal to the maximum distance from the origin vertex in the DFS traversal. In BFS algorithm (as in the aforementioned pseudo-DFS) the maximum queue size is equal to the width of the largest vertex discovery front.

最突出的和极端的例子，说明了在DFS和BFS（以及伪DFS）之间的峰值存储器消耗的差是一个星形曲线图：一个单一的中央顶点由大量（例如， 1000 ）外围顶点，与由边缘连接到中央顶点每个外围顶点。如果您在使用中央顶点为原点这个图运行BFS，队列长度将立即跳转到 1000 。同样的事情也会发生明显如果使用伪DFS（即，如果你简单地更换一个堆栈队列）。但经典的DFS算法需要的仅堆栈深度1 （！）遍历这整个图形。看到区别？ 1000 与 1 。这是由DFS更好的空间效率的意思。

The most prominent and extreme example that illustrates the difference in peak memory consumption between DFS and BFS (as well as pseudo-DFS) is a star-graph: a single central vertex surrounded by a large number (say, 1000) of peripheral vertices, with each peripheral vertex connected to the central vertex by an edge. If you run BFS on this graph using the central vertex as origin, the queue size will immediately jump to 1000. The same thing will obviously happen if you use pseudo-DFS (i.e. if you simply replace the queue with a stack). But classic DFS algorithm will need stack depth of only 1 (!) to traverse this entire graph. See the difference? 1000 versus 1. This is what is meant by better space efficiency of DFS.

基本上，采取任何书上的算法，寻找经典DFS的描述，看看它是如何工作的。你会发现，BFS和DFS之间的区别是更广泛的，一个单纯的队列与栈。

Basically, take any book on algorithms, find a description of classic DFS and see how it works. You will notice that the difference between BFS and DFS is far more extensive that a mere queue vs. stack.

P.S。还应当说，人们可以建立，将有BFS下峰值存储器消耗较小的曲线图的一个例子。因此，有关DFS更好的空间效率的声明应被视为东西，可能适用平均的一些隐含类的好的图形。

P.S. It should also be said that one can build an example of a graph that will have smaller peak memory consumption under BFS. So the statement about better space efficiency of DFS should be seen as something that might apply "on average" to some implied class of "nice" graphs.