c++ program to perform breadth first search
WRITE A PROGRAM TO PERFORM BREADTH FIRST SEARCH
#include<iostream.h>
#include<conio.h>
#include<alloc.h>
struct queue
{ int data;
queue * next; };
queue * start=NULL;
queue * tail=NULL;
queue * ptr;
queue * temp;
void enqueue (int ver )
{ if (start==NULL)
{start=(queue*)malloc(sizeof(queue));
start->data=ver;
start->next=NULL;
tail=start;
temp=start; }
else
{ ptr=(queue*)malloc(sizeof(queue));
ptr->data=ver;
temp->next=ptr;
ptr->next=NULL;
tail=ptr; temp=ptr; } }
int dequeue ( )
{ int ver = start->data;
queue * temp1=start;
start=start->next;
free(temp1);
return ver; }
void main()
{ int adj[20][20],i,j,u,no_vertex,adjvertex,vertex[20],source,colour[20],dis[20],par[20];
char choice='y'; clrscr();
for(i=0;i<20;i++)
for(j=0;j<20;j++)
adj[i][j]=0;
cout<<"Enter the number of vertex in the graph<max 20>:";
cin>>no_vertex;
for(i=0;i<no_vertex;i++)
vertex[i]=i+1;
for(;i<20;i++)
vertex[i]=-1;
for(i=0;i<no_vertex;i++)
{cout<<"\nEnter the 1st adjacent vertex of vertex "<<i+1<<":";
cin>>adjvertex;
for(j=0;j!=adjvertex-1;j++) { }
adj[i][j]=1;
cout<<"\nAny other adjacent vertex?<y,n>:";
cin>>choice;
while(choice=='y')
{ cout<<"\nEnter the next adjacent vertex of vertex "<<i+1<<":";
cin>>adjvertex;
for(j=0;j!=adjvertex-1;j++)
{ }
adj[i][j]=1;
cout<<"\nAny other adjacent vertex?<y,n>:";
cin>>choice; }
}
cout<<"\nEnter the source of the graph<vertex number>:";
cin>>source; i=0;
while(vertex[i]!=-1)
{ colour[i]=0;
dis[i]=1000;
par[i]=-1; i++; }
colour[source-1]=1;
dis[source-1]= 0 ;
par[source-1]= -1 ;
enqueue ((source-1));
while (start!=NULL)
{ u=dequeue();
for(i=0;i<no_vertex;i++)
{ if(adj[u][i]==1)
{ if(colour[i]==0)
{ colour[i]=1;
dis[i]=dis[u]+1;
par[i]=u;
enqueue(i); } } }
colour[u]=2; }
cout<<endl;
for(i=0; vertex[i]!= -1 ;i++)
{ cout<<dis[i]<<" "; }
getch(); }
OUTPUT:
