Why does a breadth first search use more memory than depth first?

Question

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.

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:

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.

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.

So why does a BFS actually use less memory?

Answer 1

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.

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

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.)

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

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.

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.

Answer 2

BFS doesn't always use more memory. The tree you have, in particular, is an example where is doesn't.

Consider this tree: (source)

With BFS, at some stage, all nodes from 8-15 will be in memory.

With DFS, you'll never have more than 4 nodes in memory (equal to the height of the tree).

The difference gets a lot worse as the tree goes larger (as long as it stays fairly full).

More specifically, BFS uses O(branchingFactor^maxDepth) or O(maxWidth) memory, where-as DFS only uses O(maxDepth).

If maxWidth < maxDepth, BFS should use less memory (assuming you use similar representations for both), but this is rarely true.

Answer 3

In general it may or may not depending on the particular graph.

A depth-first search uses a stack, which contains nodes from root to the node being searched. So at most the radius of the graph.

A breadth-first search uses a queue, which contains nodes at the front of the search. So at most all nodes at distance d.

In general graph all you can say is that it's at most all nodes in the tree in either case.

But if you have a balanced (or mostly so) k-ary tree, it's depth, i.e. radius, will be only O(log(n)), while the lowest layer will contain O(n) nodes (n/2 for binary tree and even more for higher degrees).

So depth-first search will only use O(log(n)) memory and breadth-first search will use O(n). For balanced k-ary trees; for other cases different results are possible (but for most common graphs diameter will still be significantly less than circumference).