Graph’s In Depth [PART 2]

In this article, we will discuss popular graph traversal algorithms. Before proceeding please read this article at first to get clear idea about graphs.

Graph Traversals

• BFS (Breadth First Search)

• DFS (Depth First Search)

Breadth First Search

In the Breadth First Search, the traversal is done in a level wise manner.

BFS uses Queue data structure for its implementation.

The Algorithm for BFS is as follows:

BFS(vertex){
  VISIT[]   //initialize VISIT ARRAY to 0
  QUEUE     //initialize queue
  current=vertex;
  VISIT[current]=1;
repeat  
{
  LIST[]=adjancent(current);
  for each v in LIST{
   if(VISIT[v]==0){
     QUEUE.add(v);
     VISIT[v]=1
   }
 }
 if(QUEUE.isEmpty()) return;
 x=delete from QUEUE;
 current=x;  //assign to current;
 }
}

Explaination Of Algorithm

BFS(vertex) accepts the starting vertex in the graph.

In line , VISIT[] & QUEUE is data structure to implement the BFS on graph.

VISIT[] -> is the array which represents whether the vertex has been visited or not

QUEUE -> is the data structure which stores the vertex.

We have assigned the starting vertex to variable current & on line , we have marked it visited.

Now , LIST[] array stores the list of vertices which are adjacent to current;

The for loop runs for every vertex in the LIST[] array.

If condition is cheking if the vertex is already visited,if it is not already visited,

we add that vertex in the QUEUE and mark it visited.

At last , we check is the QUEUE is EMPTY , if not Delete an element from QUEUE & assign it to current.

Just repeat the above procedure till , QUEUE is EMPTY.

DEPTH FIRST SEARCH

Depth First Search is a popular method for systematically traversing the vertices of graph.

In Depth First Search, We consider a vertex , and explore it ,until all the adjacent vertices are visited.

DFS uses stack for the implementation.

During the execution of DFS algorithm, each node of the graph will be in one of the three states indicating the visiting status of the node as follows:

• flag=1 for ready state : initial state of node
• flag=2 for waiting state : node is waiting in the stack for processing
• flag=3 for processed state: node has been processed.

The algorithm for DFS is as follows;

DFS(G){
flag=1 for all nodes
push(v1)
flag=2 for node v1
while(stack is not empty){
   x=pop()
   process(x)
   flag=3 for node x
   for all y, adjacent to x
   if(flag==1_ for y then
     push(y)
     flag=2 for y
}
}

In the next article , we will implement graph data structure in java & perform the above traversals on the graph.

Thanks for reading !