Graph searching: Breadth-first vs. depth-first
I'd like to quote an answer from Stack Overflow by hstoerr which covers the problem nicely:


  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.


Rafał Dowgird also remarks:


  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.