Graph traversal

 

Aim

Write a program to implement the graph traversal methods.

Description

Graph traversal is a technique used for searching a vertex in a graph. The graph traversal is also used to decide the order of vertices is visited in the search process. A graph traversal finds the edges to be used in the search process without creating loops. That means using graph traversal we visit all the vertices of the graph without getting into looping path.

There are two graph traversal techniques and they are as follows...

DFS (Depth First Search)

The following steps to implement DFS traversal...

Step 1 - Define a Stack of size total number of vertices in the graph.

Step 2 - Select any vertex as starting point for traversal. Visit that vertex and push it on to the Stack.

Step 3 - Visit any one of the non-visited adjacent vertices of a vertex which is at the top of stack and push it on to the stack.

Step 4 - Repeat step 3 until there is no new vertex to be visited from the vertex which is at the top of the stack.

Step 5 - When there is no new vertex to visit then use back tracking and pop one vertex from the stack.

Step 6 - Repeat steps 3, 4 and 5 until stack becomes Empty.

Step 7 - When stack becomes Empty, then produce final spanning tree by removing unused edges from the graph

BFS (Breadth First Search)

The following steps to implement BFS traversal...

Step 1 - Define a Queue of size total number of vertices in the graph.

Step 2 - Select any vertex as starting point for traversal. Visit that vertex and insert it into the Queue.

Step 3 - Visit all the non-visited adjacent vertices of the vertex which is at front of the Queue and insert them into the Queue.

Step 4 - When there is no new vertex to be visited from the vertex which is at front of the Queue then delete that vertex.

Step 5 - Repeat steps 3 and 4 until queue becomes empty.

Step 6 - When queue becomes empty, then produce final spanning tree by removing unused edges from the graph

Program

#include<stdio.h>

int q[20],top=-1,front=-1,rear=-1,a[20][20],vis[20],stack[20]; 

int delete(); 

void add(int item); 

void bfs(int s,int n); 

void dfs(int s,int n); 

void push(int item); 

int pop(); 

void main() 

{ 

int n,i,s,ch,j; 

char c,dummy; 

printf("ENTER THE NUMBER VERTICES "); 

scanf("%d",&n); 

for(i=1;i<=n;i++){ 

for(j=1;j<=n;j++) { 

printf("ENTER 1 IF %d HAS A NODE WITH %d ELSE 0: ",i,j); 

scanf("%d",&a[i][j]); 

} } 

printf("THE ADJACENCY MATRIX IS\n"); 

for(i=1;i<=n;i++) { 

for(j=1;j<=n;j++) { 

printf(" %d",a[i][j]); 

} 

printf("\n"); 

}do 

{ 

for(i=1;i<=n;i++) 

vis[i]=0; 

printf("\nMENU"); 

printf("\n1.B.F.S"); 

printf("\n2.D.F.S"); 

printf("\nENTER YOUR CHOICE"); 

scanf("%d",&ch); 

printf("ENTER THE SOURCE VERTEX :"); 

scanf("%d",&s); 

switch(ch) 

{ 

case 1:bfs(s,n); 

break; 

case 2: 

dfs(s,n); 

break; 

} 

printf("\nDO U WANT TO CONTINUE(Y/N) ? "); 

scanf("%c",&dummy); 

scanf("%c",&c); 

}while((c=='y')||(c=='Y')); 

} //**************BFS(breadth-first search) code**************// 

void bfs(int s,int n) 

{ 

int p,i; 

add(s); 

vis[s]=1; 

p=delete(); 

if(p!=0) 

printf(" %d",p); 

while(p!=0) 

{ 

for(i=1;i<=n;i++) 

if((a[p][i]!=0)&&(vis[i]==0)) 

{ 

add(i); 

vis[i]=1; 

} 

p=delete(); 

if(p!=0) 

printf(" %d ",p); 

} 

for(i=1;i<=n;i++) 

if(vis[i]==0) 

bfs(i,n); 

} 

void add(int item) 

{ 

if(rear==19) 

printf("QUEUE FULL"); 

else 

{ 

if(rear==-1) 

{ 

q[++rear]=item; 

front++; 

} 

else 

q[++rear]=item; 

} } 

int delete() 

{ 

int k; 

if((front>rear)||(front==-1)) 

return(0); 

else 

{ 

k=q[front++]; 

return(k); 

} } //***************DFS(depth-first search) code******************// 

void dfs(int s,int n) 

{ 

int i,k; 

push(s); 

vis[s]=1; 

k=pop(); 

if(k!=0) 

printf(" %d ",k); 

while(k!=0) 

{ 

for(i=1;i<=n;i++) 

if((a[k][i]!=0)&&(vis[i]==0)) 

{ 

push(i); 

vis[i]=1; 

} 

k=pop(); 

if(k!=0) 

printf(" %d ",k); 

} 

for(i=1;i<=n;i++) 

if(vis[i]==0) 

dfs(i,n); 

} 

void push(int item) 

{ 

if(top==19) 

printf("Stack overflow "); 

else 

stack[++top]=item; 

} 

int pop() 

{ 

int k; 

if(top==-1) 

return(0); 

else 

{ 

k=stack[top--]; 

return(k); 

} 

}

Output

ENTER THE NUMBER VERTICES 3 

ENTER 1 IF 1 HAS A NODE WITH 1 ELSE 0: 0 

ENTER 1 IF 1 HAS A NODE WITH 2 ELSE 0: 1 

ENTER 1 IF 1 HAS A NODE WITH 3 ELSE 0: 1 

ENTER 1 IF 2 HAS A NODE WITH 1 ELSE 0: 1 

ENTER 1 IF 2 HAS A NODE WITH 2 ELSE 0: 1 

ENTER 1 IF 2 HAS A NODE WITH 3 ELSE 0: 1 

ENTER 1 IF 3 HAS A NODE WITH 1 ELSE 0: 0 

ENTER 1 IF 3 HAS A NODE WITH 2 ELSE 0: 1 

ENTER 1 IF 3 HAS A NODE WITH 3 ELSE 0: 0 

THE ADJACENCY MATRIX IS 

0 1 1 

1 1 1 

0 1 0 

MENU 

1.B.F.S 

2.D.F.S 

ENTER YOUR CHOICE1 

ENTER THE SOURCE VERTEX :2 

2 1 3 

DO U WANT TO CONTINUE(Y/N) ? y 

MENU 

1.B.F.S 

2.D.F.S 

ENTER YOUR CHOICE2 

ENTER THE SOURCE VERTEX :2 

2 3 1 

DO U WANT TO CONTINUE(Y/N) ? N 

Result

Thus the program has been executed and verified successfully.