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

algorithm graph-algorithm graph-theory depth-first-search breadth-first-search
Parth picture Parth · Jul 26, 2010 · Viewed 255.6k times · Source

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?

Answer

Hans-Peter Störr picture Hans-Peter Störr · Jul 26, 2010

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.

Related questions

Finding all cycles in a directed graph

How can I find (iterate over) ALL the cycles in a directed graph from/to a given node? For example, I want something like this: A->B->A A->B->C->A but not: B-&…

Read More
Find all paths between two graph nodes

I am working on an implemtation of Dijkstras Algorithm to retrieve the shortest path between interconnected nodes on a network of routes. I have the implentation working. It returns all the shortest paths to all the nodes when I pass …

Read More
Relaxation of an edge in Dijkstra's algorithm

What does relaxation of an edge mean in the context of graph theory ? I came across this while studying up on Dijkstra's algorithm for single source shortest path.

Read More