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;  
 }