DFS AND BFS TRAVERSAL (AI)

The breadth first search (BFS) and the 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 a given node or not.  

Breadth First Search (BFS)

Now we take an example of a problem in BFS that is how it works what are the operations we require in order to traverse a graph with the help of BFS.

BFS means breath first search that is we can traverse the tree layerwise for example given in below 

 
Here we have have nodes A in layer one
nodes B,C,D in layer two
nodes E and F in layer three.

So now must be clear visiting the Nodes layerwise means what . For visiting a node we have queue maintaining the nodes which are visited .

Now lets see the algorithm for BFS for this tree .

• At the first layer we have A so here by convention we consider A as already marked now search for all nodes which are adjacent to A .
• Probably we find adjacent nodes to A are B,C,D so start visiting all nodes one-by one and mark all nodes as visited.
• We find B to come first so we visit B and mark it as visited then we go walk-through nodes C and D and mark them as visited.
• Traversal of all the adjacent nodes of A are B,C,D are over now A is not left with any other adjacent nodes So as by rule the one who's all Adjacent nodes are visited must be popped out of the queue.
• So finally A is popped out of the Queue and now the turns comes up for B, As B is already marked and visited go to its adjacent so we have A,E,F .
• A is popped out  B is already visited and the unvisited node is E so visit the node E and mark it as visited.
• Now similarly visit the Node F and mark it as visible,.
• Now as we have seen all the adjacent nodes of B are visited pop B out of the queue now the next node in the queue is C take C consider its Neighbor F and A .
• A is popped and F is visited so pop up C then the next member in queue is D .
• D has adjacent so pop up D Now the next member in queue is E all its neighbors are popped so eventually D will be popped up and the last element F will be pop by same means.

Depth First Search (DFS)

Depth first search has a slight different approach than BFS the Name itself suggest travels towards the Depth so first it holds a node in its hand and travel's its all the child nodes.

Here we use stack for the implementation of DFS Now we take the same example 

 

Here we visit the First node that will be A of course our root node Now control goes towards B so our second node to be visited is B then its child again so its E mark E as visited. E is left now with no more child So come one level up that is B already Visited so go to its Child that is F mark F as visited Now F is left with no Child go one level up we have C but C is already marked we have to search for its Child no child we have for C now go again one level up that is A we have its Child as B C and D but B and C are Visited D is left So visit D .

Note: The behavior of DFS  is visit the node from bottom to top .