Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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:

enter image description here

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?

like image 627
Blue7 Avatar asked May 05 '14 16:05

Blue7


People also ask

Why does BFS takes more memory than DFS?

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.

What is the difference between depth-first and Breadth-First Search?

The only difference between DFS and BFS is the order in which nodes are processed. In DFS we prioritized the deepest node in the frontier, in BFS we do the opposite. We explore all the neighbors of our starting node before exploring any other node.

What makes the depth-first search better than the Breadth-First Search in this problem?

If the searched node is shallow i.e. reachable after some edges from the origional source, then it is better to use BFS. On the other hand, if the searched node is deep i.e. reachable after a lot of edges from the origional source, then it is better to use DFS.

What are the advantages of Breadth-First Search BFS over depth-first search DFS )?

Breadth-first search is often compared with depth-first search. Advantages: A BFS will find the shortest path between the starting point and any other reachable node. A depth-first search will not necessarily find the shortest path.


2 Answers

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.

like image 191
Bernhard Barker Avatar answered Sep 20 '22 16:09

Bernhard Barker


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.

like image 30
Guffa Avatar answered Sep 20 '22 16:09

Guffa