Breadth First and Depth First Search C Language Graphs
Write a Breadth First and Depth First Search program to Represent a given graph using adjacency list and perform DFS and BFS .Use the map of the area around the college as the graph.
Breadth First and Depth First Search Code
#include
#include
#include
#include
#define MAX 20
typedef struct graph
{
char vertex[MAX];
struct graph *link;
}graph;
void breadth(graph *,int ,int );
graph *list(int);
void depth(graph *,int ,int *,int);
graph *freelist(graph *,int);
void displaylist(graph *,int);
void main()
{
int ch,*visited,s,n,i,n1,j;
graph *g=NULL;
char str2[MAX],*str;
do
{
clrscr();
printf("\n\t\tGRAPH\n\t\t2.ADJANCY LIST\n\t\t3.DISPLAY OF ADJ MAT\n\t\t4.DISPLAY OF ADJ LIST\n\t\t5.DST OF ADJ LIST\n\t\t6.BST OF ADJ LIST\n\t\t9.EXIT");
printf("\n\t\tENTER UR CHOICE:");
scanf("%d",&ch);
switch(ch)
{
case 2:
if(g!=NULL)
g=freelist(g,n);
printf("ENTER NO OF NODES");
scanf("%d",&n);
printf("\n\t\tADJANCY LIST");
g=list(n);
break;
case 4:
printf("DISPLAY OF ADJ LIST");
break;
case 5:
if(g==NULL)
printf("ENTER ADJENCY LIST FIRST");
else
{
printf("\n\t\tDST OF ADJ LIST");
while(1)
{
printf("\n\t\tENTER SOURCE");
j=0;
flushall();
gets(str2);
while(1)
{
if(strcmp(str2,(g+j)->vertex)==0)
break;
j++;
}
if(j<n) <br=""> break;
}
visited=(int *)calloc(1,sizeof(int)*n);
depth(g,j,visited,n);
printf("ISOLATED VERTEX");
for(i=0;i<n;i++) <br=""> if(*(visited+i)==0)
printf("\n\t%s",(g+i)->vertex);
free(visited);
}
getch();
break;
case 6:
if(g==NULL)
printf("ENTER ADJENCY LIST FIRST");
else
{
printf("\n\t\tBST OF ADJ LIST");
while(1)
{
printf("\n\t\tENTER SOURCE");
j=0;
flushall();
gets(str2);
while(1)
{
if(strcmp(str2,(g+j)->vertex)==0)
break;
j++;
}
if(j<n) <br=""> break;
}
breadth(g,j,n);
}
getch();
break;
case 9:
break;
}
}while(ch!=9);
}
void depth(graph *f,int i,int *visited,int n)
{
graph *t;
int j=0;
printf("\t%s",(f+i)->vertex);
*(visited+i)=1;
t=(f+i)->link;
while(t!=NULL)
{
j=0;
while(1)
{
if(strcmp(t->vertex,(f+j)->vertex)==0)
break;
j++;
}
if(*(visited+j)!=1)
depth(f,j,visited,n);
t=t->link;
}
}
graph *freelist(graph *g,int n)
{
int i;
graph *q,*p,*k;
for(i=0;i<n;i++) <br=""> {
k=(g+i);
//PRINTF("\n%d",k->vertex);
q=k->link;
while(q!=NULL)
{
//printf("\t%d",q->link);
p=q; //(remove at d tym of display)
q=q->link;
free(p);//(remove at d tym of display)
}
}
p=g;
free(p);
return NULL;
}
void breadth(graph *f,int i,int n)
{
graph *queue[MAX],*q,*t;
int *visited,front=0,rear=0,j=0;
visited=(int *)calloc(1,sizeof(int)*n);
queue[rear]=(f+i);
*(visited+i)=1;
//q=f+i;
while(front!=-1)
{
q=queue[front];
j=0;
while(1)
{
if(strcmp(q->vertex,(f+j)->vertex)==0)
break;
j++;
}
q=f+j;
if(front==rear)
front=rear=-1;
else
front=(front+1)%MAX;
printf("\t%s",q->vertex);
t=q->link;
while(t!=NULL)
{
j=0;
while(1)
{
if(strcmp(t->vertex,(f+j)->vertex)==0)
break;
j++;
}
if(*(visited+j)==0)
{
if(front==-1)
front++;
rear=(rear+1)%MAX;
queue[rear]=t;
*(visited+j)=1;
}
t=t->link;
}
}
printf("ISOLATED VERTEX");
for(j=0;j<n;j++) <br=""> if(*(visited+j)==0)
printf("\n\t%s",(f+j)->vertex);
getch();
free(visited);
}
graph * list(int n)
{
graph *g=NULL,*p,*q,*nw;
char so[MAX],de[MAX];
int s,i,d;
g=(graph *)malloc(sizeof(graph)*n);
for(i=0;i<n;i++) <br=""> {
printf("ENTER DATA");
flushall();
gets(so);
strcpy((g+i)->vertex,so);
(g+i)->link=NULL;
}
while(1)
{
printf("\n\t\tIS THERE ANY EDGES:y/n");
if(getche()=='n')
break;
printf("ENTER SOURCE & DESTINATION");
flushall();
gets(so);
flushall();
gets(de);
for(s=0;s<n;s++) <br=""> if(strcmp((g+s)->vertex,so)==0)
break;
for(d=0;d<n;d++) <br=""> if(strcmp((g+d)->vertex,de)==0)
break;
if(s==n||strcmp(so,de)==0||d==n)
printf("INVALID");
else
{
p=(g+s);
q=p->link;
while(q!=NULL)
{
if(strcmp(q->vertex,de)==0)
{
printf("ALREADY PRESENT");
break;
}
p=q;
q=q->link;
}
if(q==NULL)
{
nw=(graph *)malloc(sizeof(graph));
nw->link=NULL;
strcpy(nw->vertex,de);
p->link=nw;
p=g+d;
while(p->link!=NULL)
p=p->link;
nw=(graph *)malloc(sizeof(graph));
nw->link=NULL;
strcpy(nw->vertex,so);
p->link=nw;
}
}
}
return g;
}
