Difference between Depth First Search and Breadth First Search

Most likely, if you are traversing a tree you will be using either of these two methods: Breadth First Search or Depth First Search. Both of these methods will visit all edges and vertices of a graph but will traverse it differently.

Depth First Search will follow a path from the starting node to an ending node, then another path from start to end until all the nodes are visited. DFS starts the traversal from the root node and visits nodes as far as possible from the root node. This method is implemented using a stack data structure and generally requires less memory than BFS.

Breadth First Search proceeds level by level visiting all nodes on one level before moving on to the next. BFS starts traversal from the root node and visits nodes in a level by level manner. It is usually implemented using a queue structure and generally requires more memory than DFS.

When to use BFS vs DFS

BFS is optimal for finding the shortest distance, and is more suitable for searching vertices which are closer to the given source.

DFS is more suitable when there are solutions away from source. DFS is more suitable for game or puzzle problems. We make a decision, then explore all paths through this decision. And if this decision leads to win situation, we stop.

Comments

[Arunaa G T]

Nice

[andy]

The numbering on your DFS image is incorrect.

     0
   /   \
   1     4
  / \   / \
 2   3 5   6

[Daniel Zaltsman]

Hey Andy,

This would be true if it were a binary tree. However, this general tree is only meant to portray BFS and DFS traversal so it may not follow the same rules as a binary tree. Good catch though!