Wednesday, July 13, 2011

Difference between BFS and DFS

Breadth-first search (BFS) and depth-first search (DFS) are the two algorithms used for traversing and searching a node in a graph. They can also be used to find out whether a node is reachable from given node or not.
In depth-first search traversal  we try to go far from the root node.  Nodes are visited by going through the depth of the tree from starting node. When we reach at the node which does not have any children then we backtrack and visit the child nodes on another branch.
The depth-first search traversal of above graph will be:

A  B  E  F  C  D