为什么广度优先搜索使用的内存多于深度优先？

Question

我在网上找不到这个问题的答案,而在其他类似问题的答案中,似乎DFS的一个优点就是它使用的内存比DFS少.

对我而言,这似乎与我的期望相反.BFS只需存储它访问的最后一个节点.例如,如果我们在下面的树中搜索数字7:

它会搜索值为8的节点,然后是3,10,1,6,14,4,然后是最终的7.对于DFS,它将搜索值为8的节点,然后是3,1,6,4,最后是7 .

如果每个节点都存储在内存中,并且有关于其值,子节点以及它在树中的位置的信息,则BFS程序只需要存储有关其访问的最后一个节点的位置的信息,然后它就可以检查树,找到树中的下一个节点.DFS程序必须存储它所在的最后一个节点,以及它已经访问过的所有节点,因此它不会再次检查它们,只是循环遍历从第二代到最后一代节点之一的所有叶节点.

那么为什么BFS实际上使用更少的内存呢？

Answer 1

BFS并不总是使用更多内存.特别是,你所拥有的树就是一个不存在的例子.

考虑这棵树:( 来源)

使用BFS,在某个阶段,8-15的所有节点都将在内存中.

使用DFS,内存中永远不会有超过4个节点(等于树的高度).

随着树变大(只要它保持相当饱满),差异会变得更糟.

更具体地说,BFS使用O(branchingFactor^maxDepth)或O(maxWidth)存储,其中-DFS仅使用O(maxDepth).

如果maxWidth < maxDepth,BFS应该使用更少的内存(假设你对两者使用相似的表示),但这很少是真的.

Answer 2

可以编写搜索方法,使其只需跟踪前一个节点,但DFS比BFS更有效.

DFS只需要一次移动一级,以确定附近是否有更多节点.它将按此顺序在节点中移动以搜索所有节点:

8-3-1-3-6-4-6-7-6-3-8-10-14-13-14-10-8

每当它到达树的另一半时,BFS必须一直在树中上下移动到顶部.它将按此顺序在节点中移动:

8-3-8-10-8-3-1-3-6-3-8-10-14-10-8-3-1-6-4-6-7-6-3-8-10-14-13-14-10-8

(我不确定这是否完整,也许它甚至需要上下移动几次才能发现最后一级没有更多的节点.)

如您所见,如果要实现使用最少内存的算法,BFS的效率要低得多.

如果你想使用更多的内存来提高算法效率,那么它们最终会有大致相同的效率,基本上只能通过每个节点一次.DFS需要更少的内存,因为它只需要跟踪从顶部到底部的链中的节点,而BFS必须跟踪同一级别上的所有节点.

例如,在具有1023个节点的(平衡)树中,DFS必须跟踪10个节点,而BFS必须跟踪512个节点.

Answer 3

一般来说，它可能取决于也可能不取决于特定的图形。

深度优先搜索使用堆栈，其中包含从根节点到被搜索节点的节点。所以最多是图形的半径。

广度优先搜索使用一个队列，其中包含位于搜索前面的节点。所以至多是距离d 的所有节点。

在一般图形中，您只能说在任何一种情况下它最多都是树中的所有节点。

但是如果你有一个平衡的（或者大部分是这样的）k- ary树，它的深度，即半径，将只有 O(log( n ))，而最低层将包含 O( n ) 个节点（n /2 为二进制树，甚至更高的学位）。

所以深度优先搜索将只使用 O(log( n )) 内存，而广度优先搜索将使用 O( n )。对于平衡的k叉树；对于其他情况，可能会有不同的结果（但对于大多数常见图形，直径仍将明显小于周长）。