HSN*_*HSN 21 algorithm breadth-first-search depth-first-search graph-algorithm
在我正在考虑的算法课程中,据说深度优先搜索(DFS)比广度优先搜索(BFS)更具空间效率.
这是为什么？
虽然它们基本上都在做同样的事情,但在DFS中我们正在堆叠当前节点的后继者,而在BFS中我们将后续队列入队.
AnT*_*AnT 59
您的困惑源于这样一个事实:您显然假设可以通过用LIFO堆栈替换FIFO队列来从BFS算法获得DFS算法.
这是一种流行的误解 - 根本不是这样.通过用堆栈替换BFS队列无法获得经典的DFS算法.这些算法之间的差异更为显着.
如果您采用BFS算法并简单地将FIFO队列替换为LIFO堆栈,您将获得可称为伪DFS算法的东西.这种伪DFS算法确实会正确地再现DFS顶点前向遍历序列,但它不具有DFS空间效率,并且它不支持DFS反向遍历(回溯).
同时,真正的经典DFS无法通过这种天真的队列到堆栈替换从BFS获得.经典的DFS是一种完全不同的算法,核心结构明显不同.真正的DFS是一种真正的递归算法,它使用堆栈进行回溯,而不是用于存储顶点发现"前"(如BFS中的情况).最直接的结果是在DFS算法中,最大堆栈深度等于DFS遍历中距原点顶点的最大距离.在BFS算法中(如上述伪DFS中),最大队列大小等于最大顶点发现前沿的宽度.
说明DFS和BFS(以及伪DFS)之间峰值内存消耗差异的最突出和极端的例子是星图:由大量(例如1000)外围顶点包围的单个中心顶点,每个外围顶点通过边连接到中心顶点.如果使用中心顶点作为原点在此图上运行BFS,则队列大小将立即跳转到1000.如果你使用伪DFS(即你只是用堆栈替换队列),显然会发生同样的事情.但是经典的DFS算法只需要堆栈深度1(!)来遍历整个图形.看到不同？1000对比1.这就是DFS更好的空间效率意味着什么.
基本上,拿任何算法书,找到经典DFS的描述,看看它是如何工作的.您会注意到BFS和DFS之间的差异远远大于仅仅是队列与堆栈.
PS还应该说,人们可以建立一个图表的例子,它将在BFS下具有较小的峰值内存消耗.所以关于更好的DFS空间效率的陈述应被视为可能"平均"应用于某些隐含的"好"图的类.
在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需要空间:
在倒数第二行空间8中需要4个BFS
如果分支因子更高,情况会变得更糟