How do you know when to use DFS over BFS?

Web Development
,
#1

  • The usage of DFS heavily depends on the structure of the search tree/graph and the number and location of solutions needed. Following are the best cases where we can use DFS:

  • If it is known that the 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 take an extremely long time, but BFS could be faster.

  • If the tree is very wide, a BFS might need too much memory, so it might be completely impractical. We go for DFS in such cases.

  • If solutions are frequent but located deep in the tree we opt for DFS.

#2

As you know, DFS is a recursive algorithm, you can write it using a stack, but it does not change its recursive nature, so DO NOT USE it on infinitely deep graphs. DFS is not a complete algorithm for infinitely deep graphs (it does not guarantee to reach the goal if there is any).

Even if your graph is very deep but you have the prior knowledge that your goal is a shallow one, using DFS is not a very good idea.

Also BFS needs to keep all the current nodes in the memory, so DO NOT USE it on the graphs with high branching factor, or your computer will run out of memory very quick.

If your facing an infinitely deep graph with a high branching factor, you can use Iterative Deepening algorithm.