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