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
|
1 |
#include <br/> #include <br/> #include <br/> #include <br/> #define MAX 20 <br/> typedef struct graph <br/> { <br/> char vertex[MAX]; <br/> struct graph *link; <br/> }graph; <br/> void breadth(graph *,int ,int ); <br/> graph *list(int); <br/> void depth(graph *,int ,int *,int); <br/> graph *freelist(graph *,int); <br/> void displaylist(graph *,int); <br/> void main() <br/> { <br/> int ch,*visited,s,n,i,n1,j; <br/> graph *g=NULL; <br/> char str2[MAX],*str; <br/> do <br/> { <br/> clrscr(); <br/> 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"); <br/> printf("\n\t\tENTER UR CHOICE:"); <br/> scanf("%d",&ch); <br/> switch(ch) <br/> { <br/> case 2: <br/> if(g!=NULL) <br/> g=freelist(g,n); <br/> printf("ENTER NO OF NODES"); <br/> scanf("%d",&n); <br/> printf("\n\t\tADJANCY LIST"); <br/> g=list(n); <br/> break; <br/> case 4: <br/> printf("DISPLAY OF ADJ LIST"); <br/> break; <br/> case 5: <br/> if(g==NULL) <br/> printf("ENTER ADJENCY LIST FIRST"); <br/> else <br/> { <br/> printf("\n\t\tDST OF ADJ LIST"); <br/> while(1) <br/> { <br/> printf("\n\t\tENTER SOURCE"); <br/> j=0; <br/> flushall(); <br/> gets(str2); <br/> while(1) <br/> { <br/> if(strcmp(str2,(g+j)->vertex)==0) <br/> break; <br/> j++; <br/> } <br/> if(j<n) <br=""> break; <br/> } <br/> visited=(int *)calloc(1,sizeof(int)*n); <br/> depth(g,j,visited,n); <br/> printf("ISOLATED VERTEX"); <br/> for(i=0;i<n;i++) <br=""> if(*(visited+i)==0) <br/> printf("\n\t%s",(g+i)->vertex); <br/> free(visited); <br/> } <br/> getch(); <br/> break; <br/> case 6: <br/> if(g==NULL) <br/> printf("ENTER ADJENCY LIST FIRST"); <br/> else <br/> { <br/> printf("\n\t\tBST OF ADJ LIST"); <br/> while(1) <br/> { <br/> printf("\n\t\tENTER SOURCE"); <br/> j=0; <br/> flushall(); <br/> gets(str2); <br/> while(1) <br/> { <br/> if(strcmp(str2,(g+j)->vertex)==0) <br/> break; <br/> j++; <br/> } <br/> if(j<n) <br=""> break; <br/> } <br/> breadth(g,j,n); <br/> } <br/> getch(); <br/> break; <br/> case 9: <br/> break; <br/> } <br/> }while(ch!=9); <br/> } <br/> void depth(graph *f,int i,int *visited,int n) <br/> { <br/> graph *t; <br/> int j=0; <br/> printf("\t%s",(f+i)->vertex); <br/> *(visited+i)=1; <br/> t=(f+i)->link; <br/> while(t!=NULL) <br/> { <br/> j=0; <br/> while(1) <br/> { <br/> if(strcmp(t->vertex,(f+j)->vertex)==0) <br/> break; <br/> j++; <br/> } <br/> if(*(visited+j)!=1) <br/> depth(f,j,visited,n); <br/> t=t->link; <br/> } <br/> } <br/> graph *freelist(graph *g,int n) <br/> { <br/> int i; <br/> graph *q,*p,*k; <br/> for(i=0;i<n;i++) <br=""> { <br/> k=(g+i); <br/> //PRINTF("\n%d",k->vertex); <br/> q=k->link; <br/> while(q!=NULL) <br/> { <br/> //printf("\t%d",q->link); <br/> p=q; //(remove at d tym of display) <br/> q=q->link; <br/> free(p);//(remove at d tym of display) <br/> } <br/> } <br/> p=g; <br/> free(p); <br/> return NULL; <br/> } <br/> void breadth(graph *f,int i,int n) <br/> { <br/> graph *queue[MAX],*q,*t; <br/> int *visited,front=0,rear=0,j=0; <br/> visited=(int *)calloc(1,sizeof(int)*n); <br/> queue[rear]=(f+i); <br/> *(visited+i)=1; <br/> //q=f+i; <br/> while(front!=-1) <br/> { <br/> q=queue[front]; <br/> j=0; <br/> while(1) <br/> { <br/> if(strcmp(q->vertex,(f+j)->vertex)==0) <br/> break; <br/> j++; <br/> } <br/> q=f+j; <br/> if(front==rear) <br/> front=rear=-1; <br/> else <br/> front=(front+1)%MAX; <br/> printf("\t%s",q->vertex); <br/> t=q->link; <br/> while(t!=NULL) <br/> { <br/> j=0; <br/> while(1) <br/> { <br/> if(strcmp(t->vertex,(f+j)->vertex)==0) <br/> break; <br/> j++; <br/> } <br/> if(*(visited+j)==0) <br/> { <br/> if(front==-1) <br/> front++; <br/> rear=(rear+1)%MAX; <br/> queue[rear]=t; <br/> *(visited+j)=1; <br/> } <br/> t=t->link; <br/> } <br/> } <br/> printf("ISOLATED VERTEX"); <br/> for(j=0;j<n;j++) <br=""> if(*(visited+j)==0) <br/> printf("\n\t%s",(f+j)->vertex); <br/> getch(); <br/> free(visited); <br/> } <br/> graph * list(int n) <br/> { <br/> graph *g=NULL,*p,*q,*nw; <br/> char so[MAX],de[MAX]; <br/> int s,i,d; <br/> g=(graph *)malloc(sizeof(graph)*n); <br/> for(i=0;i<n;i++) <br=""> { <br/> printf("ENTER DATA"); <br/> flushall(); <br/> gets(so); <br/> strcpy((g+i)->vertex,so); <br/> (g+i)->link=NULL; <br/> } <br/> while(1) <br/> { <br/> printf("\n\t\tIS THERE ANY EDGES:y/n"); <br/> if(getche()=='n') <br/> break; <br/> printf("ENTER SOURCE & DESTINATION"); <br/> flushall(); <br/> gets(so); <br/> flushall(); <br/> gets(de); <br/> for(s=0;s<n;s++) <br=""> if(strcmp((g+s)->vertex,so)==0) <br/> break; <br/> for(d=0;d<n;d++) <br=""> if(strcmp((g+d)->vertex,de)==0) <br/> break; <br/> if(s==n||strcmp(so,de)==0||d==n) <br/> printf("INVALID"); <br/> else <br/> { <br/> p=(g+s); <br/> q=p->link; <br/> while(q!=NULL) <br/> { <br/> if(strcmp(q->vertex,de)==0) <br/> { <br/> printf("ALREADY PRESENT"); <br/> break; <br/> } <br/> p=q; <br/> q=q->link; <br/> } <br/> if(q==NULL) <br/> { <br/> nw=(graph *)malloc(sizeof(graph)); <br/> nw->link=NULL; <br/> strcpy(nw->vertex,de); <br/> p->link=nw; <br/> p=g+d; <br/> while(p->link!=NULL) <br/> p=p->link; <br/> nw=(graph *)malloc(sizeof(graph)); <br/> nw->link=NULL; <br/> strcpy(nw->vertex,so); <br/> p->link=nw; <br/> } <br/> } <br/> } <br/> return g; <br/> } |
Source projectgeek.com
