Traversing graph Depth first search(DFS)

 

Traversing graph using depth first search

Systematically examine the nodes and edges of a graph is called graph traversing.

Two standard way of  graph traversing

• Depth first search.
• Breath first search.

Breath first search

Breath first search will use a queue as an auxiliary structure to hold nodes for future processing.

Depth first search

Depth first search will use a stack as an auxiliary structure to hold nodes for future processing.

Each node N of Graph G will be in one of the three states called status of N. These states are

• Ready state.
• Waiting state.
• Processed state.

Depth first search

That is graph traversal technique.

That use stack as auxiliary structure to hold nodes for future processing.

Depth first search begin at starting node and as examine the starting node Then examine each node N along a path P which begins at Starting node.After coming dead end backtrack on P until we can continue along another path P'.

Algorithm Depth first on a graph G Begin at a starting node H.

 

Step 1: Initialize all nodes to the ready state.

Step 2: Push the starting node A onto STACK and change its status to the waiting state.

Step 3: Repeat steps 4 and 5 until STACK is empty.

Step 4: Pop the top node N of STACK. Process N and change its status to the processed state.

Step 5: Push onto STACK all the neighbors of N that are still in the ready state and change their status to the waiting state.

Step 6: Exit.

Example 

Print all nodes of the graph starting from node H by using depth first search(DFS) algorithm.

Solution

(a) Initially push H onto the stack

Stack :  H

(b) Pop and print the top element H and then push onto the stack all the neighbors of H.

          Print :H        Stack : A

(c) Pop and print the top element A and then push onto the stack all the neighbors of A.

        

        Print :H,A                 Stack: D,B

(d) Pop and print the top element B and then push onto the stack all the neighbors of B.

      Print: H,A,B                  Stack:D,F,C

(e) Pop and print the top element C and then push onto the stack all the neighbors of C.

  

      Print: H,A,B,C               Stack: D,F,G,E   

(f) Pop and print the top element E and then push onto the stack all the neighbors of E.

      Print:H,A,B,C,E                Stack:D,F,G  

(g) Pop and print the top element G and then push onto the stack all the neighbors of G.

     Print: H,A,B,C,E,G            Stack:D,F

(h) Pop and print the top element F and then push onto the stack all the neighbors of F.

   

    Print : H,A,B,C,E,G,F           Stack:D

(i) Pop and print the top element D and then push onto the stack all the neighbors of D.

 

    Print:H,A,B,C,E,G,F,D          Stack:

After traversing using Depth first search traversing order is 

H-A-B-C-E-G-F-D