Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

When searching graphs, there are two easy algorithms: breadth-first and depth-first (Usually done by adding all adjactent graph nodes to a queue (breadth-first) or stack (depth-first)).

Now, are there any advantages of one over another?

The ones I could think of:

  • If you expect your data to be pretty far down inside the graph, depth-first might find it earlier, as you are going down into the deeper parts of the graph very fast.
  • Conversely, if you expect your data to be pretty far up in the graph, breadth-first might give the result earlier.

Is there anything I have missed or does it mostly come down to personal preference?

share|improve this question

6 Answers 6

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.

share|improve this answer

One point that's important in our multicore world: BFS is much more easy to parallelize. This is intuitively reasonable (send off threads for each child) and can be proven to be so as well. So if you have a scenario where you can make use of parallelism, then BFS is the way to go.

share|improve this answer
4  
If DFS is otherwise advantageous in the given setting, you can apply BFS until you have spawned enough threads and continue with DFS. More specifically, you can do DFS and whenever you descend and there are not enough threads, spawn one for the next sibling. –  Raphael Mar 13 '12 at 18:16

Breadth-first and depth-first certainly have the same worst-case behaviour (the desired node is the last one found). I suspect this is also true for averave-case if you don't have information about your graphs.

One nice bonus of breadth-first search is that it finds shortest paths (in the sense of fewest edges) which may or may not be of interest.

If your average node rank (number of neighbours) is high relative to the number of nodes (i.e. the graph is dense), breadth-first will have huge queues while depth-first will have small stacks. In sparse graphs, the situation is reversed. Therefore, if memory is a limiting factor the shape of the graph at hand may have to inform your choice of search strategy.

share|improve this answer
    
The length of the queue in bfs and the height of the stack in dfs depends very much on the implementation. If in case of dfs you always expand the whole neighborhoud on the stack then it grows a lot, especially when the graph is dense. Pushing only reference that tells where to continue when dfs returns from the recursion saves a lot of space. –  uli Mar 13 '12 at 16:36

One scenario (other than finding the shortest path, which has already been mentioned) where you may have to choose one over the other to get a correct program would be infinite graphs:

If we consider for example a tree where each node has a finite number of children, but the height of the tree is infinite, DFS might never find the node you're looking for - it will just keep visiting the first child of every node it sees, so if the one you're looking for isn't the first child of its parent, it will never get there. BFS however is guaranteed to find it in finite time.

Similarly if we consider a tree where each node has an infinite number of children, but the tree has a finite height, BFS might not terminate. It will only visit the children of the root node and if the node you're looking for is the child of some other node, it won't be reached. In this case DFS is guaranteed to find it in finite time.

share|improve this answer
5  
It is noteworthy that both yield only semi-decision algorithms for infinite graphs; you can not decide in finite time that an element is not in the tree (obviously). As for practical applications, note that (conceptually) infinite data structures can be defined (see paragraph 3.4)! –  Raphael Mar 13 '12 at 13:42

(I made this a community wiki. Please feel free to edit.)

If

  • $b$ is the branching factor
  • $d$ is the depth where the solution is
  • $h$ is the height of the tree (so, $d\le h$)

Then

  • DFS takes $O(b^h)$ time and $O(h)$ space
  • BFS takes $O(b^d)$ time and $O(b^d)$ space
  • IDFS takes $O(b^d)$ time and $O(d)$ space

Reasons to choose

  • DFS
    • must see whole tree anyway
    • you know $d$, the level of the answer
    • don't care if the answer is closest to root
  • BFS
    • answer is close to the root
    • you want the answer that is closest to the root
    • have multiple cores/processors
  • IDFS
    • you want BFS, don't have enough memory, but somewhat slower is acceptable

IDFS = iterative deepening

share|improve this answer

All of the above is correct, but it's noteworthy that BFS and DFS create their own trees, based on the order they use to traverse the tree. Each of those trees has it's own property which can be useful in some sort of problems.

For example, all the edges in the original graph which are not in the BFS tree are cross edges; edges which are between two branches of the BFS tree. All the edges in the original graph which are not in the DFS tree are back edges; edges which connect two vertices in a branch of the DFS tree. Such properties can be useful for problems such as special colorings, etc.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.