为什么深度优先搜索声称可以节省空间？ [英] Why is depth-first search claimed to be space efficient?

问题描述

在我正在学习的算法课程中，据说深度优先搜索（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中，则是在排队后继者。

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.

推荐答案

您的困惑源于以下事实：您显然假设可以通过用LIFO堆栈替换FIFO队列来从BFS算法获得DFS算法。

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.

这是一个流行的误解-事实并非如此。无法通过将BFS队列替换为堆栈来获得经典的DFS算法。这些算法之间的差异要大得多。

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算法并简单地用LIFO堆栈替换FIFO队列，您将获得可以称为 pseudo-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).

同时，无法通过这种幼稚的队列到堆栈替换从BFS获得真正的经典DFS。经典的DFS是完全不同的算法，其核心结构明显不同。 True DFS是一种真正的递归算法，该算法将堆栈用于 backtracking 用途，而不是用于存储顶点发现 front（在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之间的差异远比单纯的队列vs.堆栈大。

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.

这篇关于为什么深度优先搜索声称可以节省空间？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！