When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)? [closed]

That heavily depends on the structure of the search tree and the number and location of solutions (aka searched-for items).

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

Another issue is parallelism: if you want to parallelize BFS you would need a shared datastructure between threads, which is a bad thing. DFS might be easier to distribute even between connected machines if you don’t insist on the exact order of visiting the nodes.

Leave a Comment