Study Abroad Education Loan College News Placement Book Shops E - Books Engg-Admission Edu-Classifieds Students-Forum
Easy Studies

 CPP Program For DFS and BFS #include #include #define size 20 int a[10][10],vertex[10],n,e; /*STACK FUNCTIONS*/ #define bottom -1 int stack[size],top=bottom; int stackempty() { return(top=bottom) ? 1:0; } int stackfull() { return(top==size-1) ? 1:0; } void push(int item) { if(stackfull()) printf("\nSTACK IS FULL"); else stack[++top]=item; } int pop() { if(stackempty()) { printf("\nSTACK IS EMPTY"); return -1; } else return stack[top--]; } int peep() { if(stackempty()) { printf("\n STACK IS EMPTY"); return -1; } else return stack[top]; } /* QUEUE FUNCTIONS */ #define start -1 int q[size]; int f=start,r=start; int qempty(){ return(f==r)?1:0; } int qfull(){ return(r==size-1)?1:0;} void addq(int c) { if(qfull()) printf("\nQUEUE IS FULL"); else q[++r]=c; } int delq() { if(qempty()) { printf("\nQUEUE IS EMPTY"); return -1; } else return q[++f]; } // j is unvisited adjecent vertex to i int adjvertex(int i) { int j; for(j=0;j V%d ",cur+1); addq(cur); vertex[cur]=1;//marking visited vertex while(!visitall()) { if(qempty()) { printf("\nGRAPH IS DISCONNECTED"); break; } cur=delq(); //visit all vertices which are adjecent to current vertex for(j=0;j V%d ",cur+1); push(cur); vertex[cur]=1;//marking visited vertex while(!visitall()) { do { cur=adjvertex(peep()); if(cur==n) pop(); } while(cur==n&&!stackempty()); if(stackempty()) { printf("\nGRAPH IS DISCONNECTED"); break; } if(cur!=n) { printf(" V%d ",cur+1); push(cur); vertex[cur]=1;//marking visited vertex } } } /*MAIN PROGRAM*/ void main() { int i,j,k; clrscr(); for(i=0;i<10;i++) for(j=0;j<10;j++) a[i][j]=0; printf("\nENTER NO OF VERTICES & EDGES OF UNDIRECTED GRAPH : "); scanf("%d%d",&n,&e); printf("\nENTER EDGES AS PAIR OF VERTICES"); for(k=1;k<=e;k++) { printf("EDGE %d =>",k); scanf("%d%d",&i,&j); //for undirected graph a[i-1][j-1]=1; } dfs(); bfs(); getch(); } Sample Output : ENTER NO OF VERTICES & EDGES OF UNDIRECTED GRAPH : 3 4 ENTER EDGES AS PAIR OF VERTICESEDGE 1 =>1 3 1 2 2 3 3 2 EDGE 2 =>EDGE 3 =>EDGE 4 => DFS path => V1  STACK IS EMPTY STACK IS EMPTY GRAPH IS DISCONNECTED BFS path => V1 V2 V3