Depth First Search (DFS)

 

📌Hello friends! In this post I am going to explain about Depth First Search (DFS).What is the algorithm/ How we trace algorithm by the help of example. 

Depth First Search is a Graph Traversal Methods.It is a technique used to search a vertex in a graph. It is also used to decide the order of vertices to be visited in the search process.

DFS traversal of a graph produce spanning tree as final result is a graph without loops.We use stack data structure with maximum size of total number of vertices in the graph to implement DFS traversal of a graph.

ALGORITHM FOR DEPTH FIRST SEARCH (DFS):

STEP  1 : Set status of all vertex = 1 i.e ready to process state.

STEP 2 : PUSH the starting vertex on to the STACK and set its STATUS =2 i.e                    waiting state.

STEP 3 : Repeat the following step until the stack is not empty.

     STEP 3.1 : POP the top most vertex from stack call it NODE and set STATUS                     =3  i.e processed state.

    STEP 3.2 : Now check all neighbours (adjacent vertex) of this NODE as                             follows.

          STEP 3.2.1 : If STATUS (Neighbour =1) than PUSH this neighbours on to                              the top of STACK and set its STATUS = 2 i.e waiting state.

           STEP 3.2.2 : ELSE If STATUS (Neighbour =2) than remove its previous 

                             empty from STACK and PUSH it again on to the top 

                             of STACK.

           STEP 3.2.3 : ELSE If STATUS (Neighbour =3) than leave this neighbour.

STEP 4 : END Loop

STEP 5 : end.

EXAMPLE:

let traverse the graph by using Depth First Search

Now trace the above graph using algorithm:

STEP 1: Set status of all vertex = 1 i.e ready to process state.

STEP 2:  PUSH the starting vertex on to the STACK and set its STATUS =2 i.e                  waiting state.

STEP 3 : Repeat the following step until the stack is not empty.

STEP 3.1 : POP the top most vertex from stack call it NODE and set STATUS                     =3  i.e processed state.

So in this step POP A from stack and call NODE=A, update status of A by 3. Put A in  POP vertices list.

STEP 3.2 : Now check all neighbours (adjacent vertex) of this NODE as                             follows.

So here the neighbours of A are [B , C] 

 STEP 3.2.1 : If STATUS (Neighbour =1) than PUSH this neighbours on to                              the top of STACK and set its STATUS = 2 i.e waiting state.

Again GO TO  STEP 3.1:

STEP 3.1 : POP the top most vertex from stack call it NODE and set STATUS                     =3  i.e processed state.

So in this step POP C from stack and call NODE=C, update status of C by 3. Put C in  POP vertices list.

STEP 3.2 : Now check all neighbours (adjacent vertex) of this NODE as                             follows.

So here the neighbours of C are [D , E] 

 STEP 3.2.1 : If STATUS (Neighbour =1) than PUSH this neighbours on to                              the top of STACK and set its STATUS = 2 i.e waiting state.

Again GO TO  STEP 3.1:

STEP 3.1 : POP the top most vertex from stack call it NODE and set STATUS                     =3  i.e processed state.

So in this step POP E from stack and call NODE=E, update status of E by 3. Put E in  POP vertices list.

STEP 3.2 : Now check all neighbours (adjacent vertex) of this NODE as                             follows.

So here the neighbours of E are [B , C] 

 STEP 3.2.1 : If STATUS (Neighbour =1) than PUSH this neighbours on to                              the top of STACK and set its STATUS = 2 i.e waiting state.

here the status of B & C is not equal to 1 we go with else part  i.e:

STEP 3.2.2 : ELSE If STATUS (Neighbour =2) than remove its previous 

                             empty from STACK and PUSH it again on to the top 

                             of STACK.

here on the basis of above step the status value of C=3 so leave it but the status value of B=2 So remove entry of B from stack and again enter it in top of stack such as:

Again GO TO  STEP 3.1:

STEP 3.1 : POP the top most vertex from stack call it NODE and set STATUS                     =3  i.e processed state.

So in this step POP E from stack and call NODE=B, update status of B by 3. Put B in  POP vertices list.

STEP 3.2 : Now check all neighbours (adjacent vertex) of this NODE as                             follows.

So here the neighbours of B are [A , D , E] 

 STEP 3.2.1 : If STATUS (Neighbour =1) than PUSH this neighbours on to                              the top of STACK and set its STATUS = 2 i.e waiting state.

here the status of A & E is not equal to 1 we go with else part  i.e:

STEP 3.2.2 : ELSE If STATUS (Neighbour =2) than remove its previous 

                             empty from STACK and PUSH it again on to the top 

                             of STACK.

here on the basis of above step the status value of A & E=3 so leave it but the status value of D=2 So remove entry of D from stack and again enter it in top of stack such as:

Again GO TO  STEP 3.1:

STEP 3.1 : POP the top most vertex from stack call it NODE and set STATUS                     =3  i.e processed state.

Finally we get:

In the above diagram the stack become empty so our algorithm stop here.

The path will be A → C → E → B → D

On the basis of path the graph will be:

This is also known as Depth First Spanning Tree or Depth First Traverse.

 📌Friends this is all about Depth First Search (DFS). I hope this post is helpful for understanding the concept of DFS algorithm.We will meet in next post till continue reading..