When is it it practical to use DFS vs BFS?

Question

Hi,

I understand the differences between DFS and BFS, but I'm interested to know when it's more practical to use one over the other? Could anyone give any examples of how DFS would trump BFS and vice versa? Thanks!

Answer 1

DFS is more space-efficient than BFS, but may go to unnecessary depths.

Their names are revealing: if there's a big breadth (i.e. big branching factor), but very limited depth (e.g. limited number of "moves"), then DFS can be more preferrable to BFS.

---

On IDDFS

It should be mentioned that there's a less-known variant that combines the space efficiency of DFS, but (cummulatively) the level-order visitation of BFS, is the iterative deepening depth-first search. This algorithm revisits some nodes, but it only contributes a constant factor of asymptotic difference.

Answer 2

That heavily depends on the structure of the search tree and the number and location of solutions. If you know a solution is not far from the root of the tree, a breadth first search (BFS) might be better. If the tree is very deep and solutions are rare, depth first search (DFS) might rootle around forever, but BFS could be faster. If the tree is very wide, a BFS might need too much more memory, so it might be completely impractical. If solutions are frequent but located deep in the tree, BFS could be impractical. If the search tree is very deep you will need to restrict the search depth for depth first search (DFS), anyway (for example with iterative deepening).

But these are just rules of thumb; you'll probably need to experiment.

Answer 3

xkcd Has the answer to everything ;)

This does actually genuinely demonstrate a shortfall of DFS as well as being the obligatory xkcd answer

Answer 4

Breadth First Search is generally the best approach when the depth of the tree can vary, and you only need to search part of the tree for a solution. For example, finding the shortest path from a starting value to a final value is a good place to use BFS.

Depth First Search is commonly used when you need to search the entire tree. It's easier to implement (using recursion) than BFS, and requires less state: While BFS requires you store the entire 'frontier', DFS only requires you store the list of parent nodes of the current element.

Answer 5

Some algorithms depend on particular properties of DFS (or BFS) to work. For example the Hopcroft and Tarjan algorithm for finding 2-connected components takes advantage of the fact that each already visited node encountered by DFS is on the path from root to the currently explored node.