Graph Traversals?

Graph traversals :

v   Traversing a graph is visiting all nodes exactly once in the graph.

v   The graph has no first node (or) root. Therefore the graph can be started from any node.

v   In a graph , only those nodes are traversed which are accessible from the current node complete traversing of graph the path can be determined by traversing the nodes step by step.

v   In a graph , there is a chance for a particular node can be visited repeatedly. Hence the status of every node whether traversal or not is necessary to keep.

v   In a graph , to reach a particular  node more than one path is available.

v   Each node is a graph will be in any one of the 3 status.

  Ready state (status =1)

  Waiting state (status =2)

   Visited state(status =3)

 There are 3 main graph traversal techniques

1.        Breadth first search(BFS)

2.        Depth first search(DFS)

 Breadth First Search(BFS) :

v   It was queue data structure for traversing nodes of a graph. It is similar to level by level traversal

v   To show repeated visit to the same node an array is maintained which keeps the status of visited node.

v   Any node can acts as beginning node, using this we can traverse all the nodes of graph.

The nodes which are adjacent to one starting node are processed first and proceeds adjacent  nodes of that node visited. This process is repeated until the nodes are visited.

  Algorithm :

v   Initialize all the nodes to the ready state.

v   Put the starting node in queue and changes its status to waiting (status -2)

v   Repeat step 4 & 5 until queue is empty.

v   Remove first node ‘N ‘ of queue, process N and change the status to proceeded state(status – 3)

v   Add the rear  of queue, all the neighbors of N that are in ready state(status – 1) and change their status to the waiting state.

v   Exit

Ex :      

                                         

o/p:v₁ v₂ v₃v₄ v₅ v₆ v₇ v₈

BFS V1 V2 V3 V4 V5 V6 V7 V8

Queue V2 , v3 V3 , v4, v5 V4, v5,v6, v7 V5 ,v6 ,v6 ,v8 V6, v7, v8 V7 , v8 V8 nill

Depth First Search(DFS):

v   It uses stack data structure for travelling nodes of a graph. It is similar to pre order traversal of an ordered tree.

v   A node from a graph is taken as a starting node traverse through all possible paths of the starting node.

When the last node of the graph is obtained and the path is not available from the node, then the control returns to previous state.

  Algorithm :

v   Initialize all nodes to ready state(status – 1)

v   Push starting node on the stack and change its status to the waiting(status – 2)

v   Repeat step 4 & 5 until stack is empty.

v   Pop the top node ‘N’ of stack is empty and change the status to the processed state (status – 3)

v   Push  onto state, all the neighbors of ‘N ‘ that are in ready state and change their status to the waiting state(status – 2)

v   Exit

                    

Ex:

             

o/p:v_1,  v₂ , v_4, v_8,  v_5,  v_6,  v_3, v₇

BFS V1 V2 V4 V8 V5 V6 V3 V7

Stack V2 , v3 V4 , v5, v3 V8, v5,v3 V5 ,v6 ,v7 ,v3 V6, v7, v3 V3 , v7 V7 nill