PROGRAM:
//GRAPH TRAVERSAL
#include<stdio.h> //including header files
#include<stdlib.h>
int c=0,s[16],top=-1,n=16,front=-1,rear=-1;
void push(int x) //definiton for push function
{
if(top==n) //checking if top is full
{
printf("\nstack is full");
}
else
{
top=top++; //incrementing top pointer
s[top]=x;
}
}
int pop() //definition for pop function
{
if(top<0) //checking is top is empty
{
printf("\nempty");
}
else
{
c=s[top]; //retuning or poping the element
top=top--;
return c;
}
}
void enqueue(int x)
{ //definiton for enqueue function
if(rear==n) //checking if queue is full
{
printf("\nstack is full");
}
else
{
if(rear==-1)
{
rear=rear++;
front=rear;
}
s[rear]=x;
rear=rear++;
}
}
int dequeue() //definition for dequeue function
{
if(front<0) //checking is queue is empty
{
printf("\nempty");
}
else if(front==rear)
{
front=rear=-1;
}
else
{
c=s[front]; //returning or dequeueing the element
front=front++;
return c;
}
}
int main()
{
system("clear");
int a[5][5],i,j,t,x1,s1[5],ch;
for(i=1;i<=4;i++)
{
for(j=1;j<=4;j++)
{
printf("\nEnter whether adjacency exists from %d to %d : ",i,j);
scanf("%d",&a[i][j]); //getting adjacency from user
}
}
for(i=1;i<=4;i++)
{
s1[i]=0;
}
do
{
printf("\n1.Depth first search\n2.Breadth first search\n3.Exit\n3.Exit\n3.Exit\n");
scanf("%d",&ch);
switch(ch)
{
case 1: //implementing menu driven manner
{
for(i=1;i<=4;i++)
{
s1[i]=0;
}
printf("\nEnter the source node\t:");
scanf("%d",&x1); //getting the source node
push(x1);
while(top!=-1)
{
t=pop();
if(s1[t]==0)
{
printf("%d",t);
s1[t]=1;
for(j=1;j<=4;j++)
{
if(a[t][j]==1)
{
push(j);
}
}
}
}
break;
}
case 2:
{
for(i=1;i<=4;i++)
{
s1[i]=0;
}
printf("\nEnter the source node\t:");
scanf("%d",&x1); //getting the source node
enqueue(x1);
while(front>=0)
{
t=dequeue();
if(s1[t]==0)
{
printf("%d",t);
s1[t]=1;
for(j=1;j<=4;j++)
{
if(a[t][j]==1)
{
enqueue(j);
}
}
}
}
break;
}
}
}while(ch!=3);
return 0;
}
OUTPUT:
Enter whether adjacency exists from 1 to 1 : 0
Enter whether adjacency exists from 1 to 2 : 1
Enter whether adjacency exists from 1 to 3 : 1
Enter whether adjacency exists from 1 to 4 : 1
Enter whether adjacency exists from 2 to 1 : 0
Enter whether adjacency exists from 2 to 2 : 0
Enter whether adjacency exists from 2 to 3 : 1
Enter whether adjacency exists from 2 to 4 : 1
Enter whether adjacency exists from 3 to 1 : 0
Enter whether adjacency exists from 3 to 2 : 0
Enter whether adjacency exists from 3 to 3 : 0
Enter whether adjacency exists from 3 to 4 : 0
Enter whether adjacency exists from 4 to 1 : 0
Enter whether adjacency exists from 4 to 2 : 0
Enter whether adjacency exists from 4 to 3 : 1
Enter whether adjacency exists from 4 to 4 : 0
1.Depth first search
2.Breadth first search
3.Exit
1
Enter the source node :1
1432
1.Depth first search
2.Breadth first search
3.Exit
2
Enter the source node :1
1234
1.Depth first search
2.Breadth first search
3.Exit3
No comments:
Post a Comment