为什么广度优先搜索比深度优先使用更多的内存？ [英] Why does a breadth first search use more memory than depth first?

问题描述

我在网上找不到答案，在其他类似问题的答案中，似乎可以肯定的是，DFS的优点是它使用的内存少于DFS。

I can't find an answer to this online, and in other answers to questions similar to this it just seems to be a given that an advantage of DFS is that it uses less memory than DFS.

对我来说，这似乎与我期望的相反。 BFS只需存储它访问的最后一个节点。例如，如果我们在下面的树中搜索数字7：

To me this seems the opposite to what I would expect. A BFS only has to store the last node it visited. For example if we are searching for the number 7 in the tree below:

它将搜索值为8，然后为3、10、1、6、14、4，最后为7的节点对于DFS，它将搜索值为8，然后为3、1、6、4，最后为7的节点。

It will search the node with value 8, then 3, 10, 1, 6, 14, 4, then finaly 7. For a DFS it will search the node with value 8, then 3, 1, 6, 4, then finally 7.

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

If each node is stored in the memory, with information about its value, its children, and it position in the tree then a BFS program will only need to store the information about the position of the last node it visited, then it can check the tree and find the next node in the tree. A DFS program has to store the last node it was at, as well as all the nodes it has already visited so it doesn't check them again and just cycle through all the leaf nodes coming off one of the second to last generation nodes.

为什么BFS实际上使用较少的内存？

So why does a BFS actually use less memory?

推荐答案

可以编写两种搜索方法，以便只跟踪先前的节点，但是DFS则更多

Either search method can be written so that it only has to keep track of the previous node, but then the DFS is more efficient than the BFS.

DFS一次只需要经过一层，即可确定附近是否还有更多的节点。它将按照以下顺序遍历所有节点：

The DFS only has to travel one level at a time to find out if there are more nodes nearby. It would move through the nodes in this order to search trough all of them:

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

只要BFS到达树的另一半，它就必须一直沿树上下移动。它将按以下顺序在节点之间移动：

The BFS has to travel up and down the tree all the way to the top whenever it goes to the other half of the tree. It would move through the nodes in this order:

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

（我不确定这是否完成，也许它甚至还要上下移动几次才能找出答案

(I'm not certain if that is complete though, perhaps it even has to travel up and down a few more times to find out that there are no more nodes on the last level.)

如您所见，如果您想实现一个使用最少的节点的算法，则BFS的效率要低得多。内存。

As you see, the BFS is a lot less efficient if you want to implement an algorithm that uses a minimum of memory.

如果您想使用更多的内存来提高算法的效率，那么它们最终将具有大致相同的效率，基本上只需要遍历每个节点一次。 DFS需要较少的内存，因为它只需要跟踪从上到下的链中的节点，而BFS则必须跟踪在同一级别上的所有节点。

If you want to use more memory to make the algorithms more efficient, then they end up having roughly the same efficiency, basically only going through each node once. The DFS needs less memory as it only has to keep track of the nodes in a chain from the top to the bottom, while the BFS has to keep track of all the nodes on the same level.

例如，在一个具有1023个节点的（平衡）树中，DFS必须跟踪10个节点，而BFS必须跟踪512个节点。

For example, in a (balanced) tree with 1023 nodes the DFS has to keep track of 10 nodes, while the BFS has to keep track of 512 nodes.

这篇关于为什么广度优先搜索比深度优先使用更多的内存？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！