为什么深度优先搜索声称可以节省空间？
在我正在学习的算法课程中，据说 深度优先搜索 （DFS）比 广度优先搜索 （BFS）的空间效率要高得多。
这是为什么？
尽管他们基本上在做相同的事情，但是在DFS中我们堆叠了当前节点的后继者，而在BFS中我们正在排队后继者。
回答：
您之所以困惑，是因为您显然假设可以通过使用LIFO堆栈替换FIFO队列来从BFS算法获得DFS算法。
这是一个普遍的误解-事实并非如此。无法通过将BFS队列替换为堆栈来获得经典的DFS算法。这些算法之间的差异要大得多。
如果您采用BFS算法，而只是用LIFO堆栈替换FIFO队列，则将获得可以称为 伪DFS
算法的内容。该伪DFS算法确实可以正确地重现DFS顶点的正向遍历序列，但是它不具有DFS空间效率，并且不支持DFS反向遍历（回溯）。
同时，通过这种幼稚的队列到堆栈替换无法从BFS获得真正的经典DFS。经典的DFS是完全不同的算法，其核心结构明显不同。True DFS是一种真正的 递归
算法，使用堆栈进行 回溯 ，而不是用于存储顶点发现“
front”（就像BFS一样）。最直接的后果是，在DFS算法中，最大堆栈深度等于DFS遍历中距原点的最大距离。在BFS算法中（如上述伪DFS），最大队列大小等于最大顶点发现前沿的宽度。
最显眼和极端的例子说明了DFS和BFS（以及伪DFS）之间的峰值内存消耗差异，这是一个星图：一个中心顶点被大量（例如1000）外围顶点包围，并且每个外围顶点通过一条边连接到中心顶点。如果您使用中心顶点作为原点在此图上运行BFS，则队列大小将立即跳至1000。如果使用伪DFS（即，简单地将队列替换为堆栈），则显然会发生相同的事情。但是经典的DFS算法只需要1（！）的堆栈深度即可遍历整个图形。看到不同？1000与1。这就是DFS更好的空间效率的意思。
基本上，请阅读有关算法的任何书籍，找到对经典DFS的描述，并查看其工作原理。您会注意到，BFS和DFS之间的区别远比单纯的队列vs.堆栈大得多。
PS还应该说，可以构建一个图表示例，该图表在BFS下的峰值内存消耗较小。因此，关于DFS更好的空间效率的陈述应被视为可以“平均”应用于某些隐含的“漂亮”图类。
以上是 为什么深度优先搜索声称可以节省空间？ 的全部内容， 来源链接： utcz.com/qa/402934.html
