Graph Traversal - Depth First Search

Depth First Search is used to perform traversal of a graph. In this method, all the vertices are stored in a Stack and each vertex of the graph is visited or explored once. The newest vertex (added last) in the Stack is explored first. To traverse the graph, Adjacent List of a graph is created first.

EXAMPLE

For Example : Consider the following Graph

The Adjacent List is

11 -> 12,18,13

12-> 11,14,15

13-> 11,16,17

14-> 12,18

15-> 12,18

16-> 13,18

17-> 13,18

18-> 14,15,11,16,17

Let us suppose that starting node is 11, The steps to traverse graph using Depth First Search is

Step 1: Push 11 onto the Stack

Stack: 11

Step 2:  Pop the top element i.e. last added (11) from the stack and push all adjacent vertex of popped vertex onto the stack that are not visited.

Stack:  12,18,13

Step 3:  Pop the top element i.e. last added (13) from the stack and push all adjacent vertex of popped vertex onto the stack that are not visited.

Stack: 12,18,16,17

11 not added becoz already visited; i.e. onto stack or deleted

Step 4:  Pop the top element i.e. last added (17) from the stack and push all adjacent vertex of popped vertex onto the stack that are not visited.

Stack: 12,18,16

13 and 18 not added becoz already visited; i.e. onto stack or deleted

Step 5:  Pop the top element i.e. last added (16) from the stack and push all adjacent vertex of popped vertex onto the stack that are not visited.

Stack: 12,18

13 and 18 not added becoz already visited; i.e. onto stack or deleted

Step 6:  Pop the top element i.e. last added (18) from the stack and push all adjacent vertex of popped vertex onto the stack that are not visited.

Stack: 12,14,15

11,16 and 17 not added becoz already visited; i.e. onto stack or deleted

 

Step 7:  Pop the top element i.e. last added (15) from the stack and push all adjacent vertex of popped vertex onto the stack that are not visited.

Stack: 12,14

12 and 18  not added becoz already visited; i.e. onto stack or deleted

Step 8:  Pop the top element i.e. last added (14) from the stack and push all adjacent vertex of popped vertex onto the stack that are not visited.

Stack: 12

12 and 18  not added becoz already visited; i.e. onto stack or deleted

 

Step 9:  Pop the top element i.e. last added (12) from the stack and push all adjacent vertex of popped vertex onto the stack that are not visited.

Stack: ----

11, 14 and 15  not added becoz already visited; i.e. onto stack or deleted

Stack Empty. Therefore the Depth First Search is  11,13,17,16,18, 15,14,12

METHOD

Step 1: Intialise all the vertices.

Step 2: Push starting vertex onto the Stack.

Step 3: Repeat step 4 and 5 until Stack is empty.

Step 4: Pop the top vertex from the Stack.

Step 5: Push onto stack all the neighbours of Popped vertex

Step 6: Exit

ALGORITHM

Step 1: currentNode=startNode

Step 2: visited[startNode]=1

Step 3: Repeat

             { for all vertex w adjacent from currentNode

                 {      if (visited[w]==0)

                                { PUSH(w)

                                visited[w]=1

                                }

                 }

           If Q is empty then return

                Else  POP(currentNode)

         }