BFS AND DFS Algorithm using C Language

Represent a given graph using adjacency list and perform BFS AND DFS Algorithm. Use the map of the area around the college as the graph. Identify the prominent land marks as nodes and perform DFS and BFS on that.

BFS AND DFS Algorithm Code

 
 #include  
 #include  
 #include  
 #define MAX 30  
 typedef struct tree  
 {  
 char data[7];  
 struct tree *lc;  
 struct tree *rc;  
 }tree;  
 typedef struct stack1  
 {  
 int flag;  
 struct tree * addr;  
 struct stack1 *link;  
 }stack1;  
 tree *alloc();  
 tree * create();  
 tree * insert(tree *);  
 void recin(tree *);  
 void recpost(tree *);  
 void recpre(tree *);  
 void itin(tree *);  
 void itpost(tree *);  
 void itpre(tree *);  
 tree *delet(tree *,char[]);  
 tree *parent(tree *,tree *);  
 tree *succ(tree *,tree *);  
 tree *pre(tree *,tree *);  
 void search(tree *,char[]);  
 tree *search1(tree *,char[],int * );  
 void leveldis(tree *);  
 tree *mirror(tree *);  
 tree * freeall(tree *);  
 int depth(tree *,char[]);  
 int height(tree *);  
 void main()  
 {  
 int i=0,ch,ch1,data;  
 char d[7];  
 tree *f=NULL,*f1=NULL;  
 do  
 {  
 clrscr();  
 printf("\n\t\tBST TREE OPERATION\n\t\t1.CREATE\n\t\t2.INSERT\n\t\t3.DELETE");  
 printf("\n\t\t4.SEARCH\n\t\t5.RECURSIVE TRAVERSE\n\t\t6.ITERATIVE TRAVERSE");  
 printf("\n\t\t7.DEPTH OF TREE\n\t\t8.MIRROR IMAGE\n\t\t9.LEVEL WISE DISPLAY MIRROR IMAGE\n\t\t10.HEIGHT OF TREE\n\t\t11.EXIT\n\t\tENTER UR CHOICE");  
 scanf("%d",&ch);  
 switch(ch)  
 {  
 case 1:  
 if(f!=NULL)  
 f=freeall(f);  
 printf("\n\t\tCREATE");  
 f=create();  
 break;  
 case 2:  
 if(f==NULL)  
 printf("CREATE FIRST");  
 else  
 {  
 printf("\n\t\tINSERT");  
 f=insert(f);  
 }  
 break;  
 case 3:  
 if(f==NULL)  
 printf("CREATE FIRST");  
 else  
 {  
 printf("\n\t\tDELETE\n\t\tENTER DATA");  
 flushall();  
 gets(d);  
 f=delet(f,d);  
 }  
 break;  
 case 4:  
 if(f==NULL)  
 printf("CREATE FIRST");  
 else  
 {  
 printf("\n\t\tSEARCH\n\t\tENTER DATA");  
 flushall();  
 gets(d);  
 search(f,d);  
 }  
 break;  
 case 5:  
 if(f==NULL)  
 printf("\n\t\tENTER INPUT FIRST");  
 else  
 do  
 {  
 clrscr();  
 printf("\n\t\tRECURSIVE TRAVERSE MENU\n\t\t1.INORDER\n\t\t2.POSTORDER\n\t\t3.PREORDER\n\t\t4.EXIT");  
 scanf("%d",&ch1);  
 switch(ch1)  
 {  
 case 1:  
 printf("\n\t\tINORDER");  
 recin(f);  
 break;  
 case 2:  
 printf("\n\t\tPOSTORDER");  
 recpost(f);  
 break;  
 case 3:  
 printf("\n\t\tPREORDER");  
 recpre(f);  
 break;  
 case 4:  
 break;  
 default:  
 printf("\n\t\tINVALID CHOICE");  
 }  
 getch();  
 }while(ch1!=4);  
 getch();  
 break;  
 case 6:  
 if(f==NULL)  
 printf("\n\t\tENTER INPUT FIRST");  
 else  
 do  
 {  
 clrscr();  
 printf("\n\t\tITERATIVE TRAVERSE MENU\n\t\t1.INORDER\n\t\t2.POSTORDER\n\t\t3.PREORDER\n\t\t4.EXIT");  
 scanf("%d",&ch1);  
 switch(ch1)  
 {  
 case 1:  
 printf("\n\t\tINORDER");  
 itin(f);  
 break;  
 case 2:  
 printf("\n\t\tPOSTORDER");  
 itpost(f);  
 break;  
 case 3:  
 printf("\n\t\tPREORDER");  
 itpre(f);  
 break;  
 case 4:  
 break;  
 default:  
 printf("\n\t\tINVALID CHOICE");  
 }  
 }while(ch1!=4);  
 getch();  
 break;  
 case 7:  
 if(f==NULL)  
 printf("CREATE FIRST");  
 else  
 {  
 printf("\n\t\tDEPTH OF TREE\n\t\tENTER DATA");  
 flushall();  
 gets(d);  
 i=depth(f,d);  
 if(i!=-1)  
 printf("DEPTH OF GIVEN NODE IS %d",i);  
 getch();  
 }  
 break;  
 case 8:  
 if(f==NULL)  
 printf("CREATE FIRST");  
 else  
 {  
 if(f1!=NULL)  
 f1=freeall(f1);  
 printf("\n\t\tMIRROR OF TREE");  
 f1=mirror(f);  
 recin(f1);  
 getch();  
 }  
 break;  
 case 9:  
 if(f1==NULL)  
  printf("CREATE MIRROR IMAGE FIRST");  
 else  
 {  
 printf("\n\t\tLEVEL WISE MIRROR OF TREE");  
 leveldis(f1);  
 }  
 break;  
 case 10:  
 if(f==NULL)  
  printf("CREATE FIRST");  
 else  
 {  
 printf("\n\t\theight OF TREE:");  
 i=height(f);  
 printf("%d",i);  
 }  
 break;  
 case 11:  
 break;  
 }  
 getch();  
 }while(ch!=11);  
 }  
 tree * create()  
 {  
 tree *root=NULL;  
 do  
 {  
 root=insert(root);  
 printf("DO U WANT TO ENTER MORE");  
 }while(getche()=='y'||getche()=='Y');  
 return root;  
 }  
 tree *alloc()  
 {  
 tree *nw;  
 nw=(tree *)malloc(sizeof(tree));  
 nw->lc=nw->rc=NULL;  
 printf("ENTER DATA");  
 flushall();  
 gets(nw->data);  
 return nw;  
 }  
 tree * insert(tree *root)  
 {  
 tree *nw,*t;  
 nw=alloc();  
 if(root==NULL)  
 return nw;  
 t=root;  
 while(1)  
 {  
 if(strcmp(nw->data,t->data)<0)  
 {  
 if(t->lc==NULL)  
 {  
 t->lc=nw;  
 return root;  
 }  
 t=t->lc;  
 }  
 else if(strcmp(nw->data,t->data)>0)  
 {  
 if(t->rc==NULL)  
 {  
 t->rc=nw;  
 return root;  
 }  
 t=t->rc;  
 }  
 else  
 {  
 printf("ALREADY PRESNT");  
 free(nw);  
 break;  
 }  
 }  
 return root;  
 }  
 void recin(tree *root)  
 {  
 if(root!=NULL)  
 {  
 recin(root->lc);  
 puts(root->data);  
 recin(root->rc);  
 }  
 }  
 void recpost(tree *root)  
 {  
 if(root!=NULL)  
 {  
 recpost(root->lc);  
 recpost(root->rc);  
 puts(root->data);  
 }  
 }  
 void recpre(tree *root)  
 {  
 if(root!=NULL)  
 {  
 puts(root->data);  
 recpre(root->lc);  
 recpre(root->rc);  
 }  
 }  
 void itin(tree *root)  
 {  
 tree *t;  
 tree *st[30];  
 int top=-1;  
 t=root;  
 while(t!=NULL||top!=-1)  
 {  
 if(t!=NULL)  
 {  
 st[++top]=t;  
 t=t->lc;  
 }  
 else  
 {  
 t=st[top--];  
 puts(t->data);  
 t=t->rc;  
 }  
 }  
 getch();  
 }  
 void itpre(tree *root)  
 {  
 tree *t;  
 tree *st[30];  
 int top=-1;  
 t=root;  
 while(t!=NULL||top!=-1)  
 {  
 if(t!=NULL)  
 {  
 puts(t->data);  
 st[++top]=t;  
 t=t->lc;  
 }  
 else  
 {  
 t=st[top--];  
 t=t->rc;  
 }  
 }  
 getch();  
 }  
 void itpost(tree *root)  
 {  
 tree *t;  
 stack1 *top,*nw;  
 top=NULL;  
 t=root;  
 while(t!=NULL||top!=NULL)  
 {  
 if(t!=NULL)  
 {  
 nw=(stack1 *)malloc(sizeof(stack1));  
 nw->addr=t;  
 nw->link=top;  
 nw->flag=0;  
 top=nw;  
 t=t->lc;  
 }  
 else  
 {  
 t=top->addr;  
 if(top->flag==0)  
 {  
 top->flag=1;  
 t=t->rc;  
 }  
 else  
 {  
 puts(t->data);  
 nw=top;  
 top=top->link;  
 free(nw);  
 t=NULL;  
 }  
 }  
 }  
 getch();  
 }  
 tree * freeall(tree *t)  
 {  
 tree * q;  
 q=t;  
 if(t!=NULL)  
 {  
 t=freeall(t->lc);  
 t=freeall(q->rc);  
 free(q);  
 }  
 return NULL;  
 }  
 tree *delet(tree *root,char val[])  
 {  
 tree *d,*s,*c,*p,*node;  
 int i=0;  
 p=root;  
 node=search1(root,val,&i);  
 if(i!=0)  
 {  
 if(node->rc!=NULL&&node->lc!=NULL)  
 {  
 printf("WANT TO DELETE BY SUCCESSOR PRESS 'y' ,PRESS ANY KEY FOR PREDECCESOR");  
 if(getche()=='y')  
 s=succ(root,node);  
 else  
 s=pre(root,node);  
 }  
 else  
 s=node;  
 if(s->lc!=NULL)  
 c=s->lc;  
 else  
 c=s->rc;  
 p=parent(root,s);  
 if(p==NULL)  
 {  
 root=c;  
 free(root);  
 return c;  
 }  
 if(p->lc==s)  
 p->lc=c;  
 else  
 p->rc=c;  
 if(s!=node)  
 strcpy(node->data,s->data);  
 free(s);  
 printf("DELETED");  
 }  
 else  
 printf("NOT FOUND");  
 getch();  
 return root;  
 }  
 tree *parent(tree *root,tree *node)  
 {  
 tree *p;  
 p=root;  
 if(strcmp(p->data,node->data)==0)  
 p=NULL;  
 else  
 while(p!=NULL)  
 {  
 if(strcmp(p->data,node->data)<0)  
 {  
 if(p->rc==node)  
 return p;  
 p=p->rc;  
 }  
 else  
 {  
 if(p->lc==node)  
 break;  
 p=p->lc;  
 }  
 }  
 return p;  
 }  
 tree *succ(tree *root,tree *node)  
 {  
 tree *t,*p;  
 if(node->rc!=NULL)  
 {  
 t=node->rc;  
 while(t->lc!=NULL)  
 t=t->lc;  
 return t;  
 }  
 t=node;  
 p=parent(root,node);  
 while(p->lc!=t&&t!=NULL)  
 {  
 t=p;  
 p=succ(root,t);  
 }  
 return p;  
 }  
 tree *pre(tree *root,tree *node)  
 {  
 tree *t,*p;  
 if(node->lc!=NULL)  
 {  
 t=node->lc;  
 while(t->rc!=NULL)  
 t=t->rc;  
 return t;  
 }  
 t=node;  
 p=parent(root,node);  
 while(p->rc!=t&&t!=NULL)  
 {  
 t=p;  
 p=succ(root,t);  
 }  
 return p;  
 }  
 void search(tree *root,char val[])  
 {  
 tree *t,*q;  
 t=root;  
 if(strcmp(val,root->data)!=0)  
 {  
 if(strcmp(val,t->data)>0)  
 q=t->rc;  
 else if(strcmp(val,t->data)<0)  
 q=t->lc;  
 while(q!=NULL)  
 {  
 if(strcmp(val,q->data)>0)  
 q=q->rc;  
 else if(strcmp(val,q->data)<0)  
 q=q->lc;  
 else  
 break;  
 if(strcmp(q->data,t->data)>0)  
 t=t->rc;  
 else if(strcmp(q->data,t->data)<0)  
 t=t->lc;  
 }  
 }  
 else  
 q=root;  
 if(q==NULL)  
 printf("\nNOT FOUND");  
 else  
 {  
 if(q==root)  
 printf("\nIT IS ROOT NODE");  
 else  
 {  
 printf("\nITS PARENT IS:");  
 puts(t->data);  
 }  
 if(q->lc==NULL&&q->rc==NULL)  
 printf("\nIT IS A LEAF NODE");  
 else  
 {  
 if(q->lc!=NULL)  
 {  
 printf("\nITS LEFT CHILD IS:");  
 puts(q->lc->data);  
 }  
 else  
 printf("\nLEFT CHILD IS NOT PRESENT");  
 if(q->rc!=NULL)  
 {  
 printf("\nITS RIGHT CHILD IS:");  
 puts(q->rc->data);  
 }  
 else  
 printf("\nRIGHT CHILD IS NOT PRESENT");  
 }  
 }  
 getch();  
 }  
 tree *mirror(tree *root)  
 {  
 tree *t,*q,*f=NULL,*nw;  
 tree *st[20][2];  
 int top=-1;  
 t=root;  
 while(t!=NULL||top!=-1)  
 {  
 nw=(tree *)malloc(sizeof(tree));  
 nw->lc=NULL;  
 nw->rc=NULL;  
 if(t==NULL)  
 {  
 t=st[top][0];  
 q=st[top--][1];  
 q->lc=nw;  
 q=q->lc;  
 }  
 else if(t!=root)  
 {  
 q->rc=nw;  
 q=q->rc;  
 }  
 if(f==NULL)  
 {  
 f=nw;  
 q=f;  
 }  
 strcpy(q->data,t->data);  
 if(t->rc!=NULL)  
 {  
 st[++top][0]=t->rc;  
 st[top][1]=q;  
 }  
 t=t->lc;  
 }  
 return f;  
 }  
 void leveldis(tree *f)  
 {  
 tree *queue[MAX],*t;  
 int front=-1,rear=-1,i=-1,pl=0,cl=1;  
 t=f;  
 if(front==-1)  
 front++;  
 rear=(rear+1)%MAX;  
 queue[rear]=t;  
 while(cl!=0||pl!=0)  
 {  
 if(pl==0)  
 {  
 i++;  
 printf("\nELEMENT IN %d LEVEL:",i);  
 pl=cl;  
 cl=0;  
 }  
 t=queue[front];  
 if(front==rear)  
 front=rear=-1;  
 else  
 front=(front+1)%MAX;  
 puts(t->data);  
 if(t->lc!=NULL)  
 {  
 if(front==-1)  
 front++;  
 rear=(rear+1)%MAX;  
 queue[rear]=t->lc;  
 cl++;  
 }  
 if(t->rc!=NULL)  
 {  
 if(front==-1)  
 front++;  
 rear=(rear+1)%MAX;  
 queue[rear]=t->rc;  
 cl++;  
 }  
 pl--;  
 }  
 getch();  
 }  
 int depth(tree *root,char val[])  
 {  
 tree *t,*node;  
 int i=0;  
 t=root;  
 while(t!=NULL)  
 {  
 if(strcmp(val,t->data)==0)  
 return i;  
 else if(strcmp(val,t->data)<0)  
 {  
 i++;  
 t=t->lc;  
 }  
 else  
 {  
 i++;  
 t=t->rc;  
 }  
 }  
 printf("NOT FOUND");  
 getch();  
 return -1;  
 }  
 tree* search1(tree *root,char val[],int *i)  
 {  
 tree *t;  
 t=root;  
 while(t!=NULL)  
 {  
 if(strcmp(val,t->data)>0)  
 t=t->rc;  
 else if(strcmp(val,t->data)<0)  
 t=t->lc;  
 else  
 {  
 *i=1;  
 break;  
 }  
 }  
 return t;  
 }  
 int height(tree *t)  
 {  
 int hl,hr;  
 if(t==NULL)  
 return 0;  
 if(t->lc==NULL&&t->rc==NULL)  
 return 0;  
 hl=height(t->lc);  
 hr=height(t->rc);  
 if(hl>hr)  
 return(hl+1);  
 return(hr+1);  
 }