Graph Traversal - Breadth First Search

Breadth First Search can be used to find the shortest distance between some starting vertex and remaining vertex of the graph. In this method, all the vertices are stored in a Queue and each vertex of the graph is visited or explored once. The oldest vertex (added first) in the Queue is explored first. To traverse the graph using breadth first search, 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 Breadth First Search Is

Step 1: Add 11 to queue

Front: 1                    Queue: 11

Rear:1

Step 2: Delete element at Front  position (11) and add all the adjacent nodes of deletd not that are not visited.

Front: 2                    Queue: X,12, 18, 13

Rear:4

Step 3: Delete element at Front position (12) and add all the adjacent nodes of deletd not that are not visited.

Front: 3                    Queue: X,X,18, 13, 14, 15           

Rear:6

 11 already visited; i.e. in Queue or deleted

Step 4: Delete element at Front position (18) and add all the adjacent nodes of deletd not that are not visited.

Front: 4                    Queue: X,X,X,13, 14, 15, 16,17        

Rear:8

11,14,15 already visited; i.e. in Queue or deleted

Step 5: Delete element at Front position (13) and add all the adjacent nodes of deletd not that are not visited.

Front: 5                    Queue: X,X,X,X, 14, 15, 16,17        

Rear:8

No vertex added becoz 11,16,17 already visited; i.e. in Queue or deleted

Step 6: Delete element at Front position (14) and add all the adjacent nodes of deletd not that are not visited.

Front: 6                    Queue: X,X,X,X, X, 15, 16,17       

Rear:8

No vertex added becoz 12 and 18 already visited; i.e. in Queue or deleted

Step 7: Delete element at Front position (15) and add all the adjacent nodes of deletd not that are not visited.

Front: 7                    Queue: X,X,X,X, X,X,16,17      

Rear:8

No vertex added becoz 12 and 18 already visited; i.e. in Queue or deleted

Step 8: Delete element at Front position (16) and add all the adjacent nodes of deletd not that are not visited.

Front: 8                    Queue: X,X,X,X, X,X,X,17      

Rear:8

No vertex added becoz 13 and 18 already visited; i.e. in Queue or deleted

Step 9: Delete element at Front position (17) and add all the adjacent nodes of deletd not that are not visited.

Front: 8                   Queue: X,X,X,X, X,X,X,X      

Rear:8

No vertex added becoz 13 and 18 already visited; i.e. in Queue or deleted

Queue EMPTY. STOP.

Therefore Breadth First Search is 11,12,18,13,14,15,16,17

ALGORITHM

Step 1: Initialize all the vertices and create adjacent list.

Step 2: Put Starting vertex in Queue.

Step 3: Repeat Step 4 and 5 until Queue is empty.

Step 4: Remove front node from the Queue.

Step 5: Add to the rear of the Queue all the neighbors of the deleted node that are not visited or added in a Queue.

Step 6: Exit

APPLICATIONS

1. Used to test whether graph is connected or not
2. To find the cycles in the graphs
3. To find the path with minimum number of edges between start vertex and current vertex or reporting that no such path exists.

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)

         }