#include
#include
#include
struct edge
{
int destin;
struct edge *edgeptr;
};

struct graph
{
int reach[6];
int nodeno[6];
char data[6];
int dist[6];
struct edge *listptr[6];
};

void main()
{
struct graph g1;
void bfs(struct graph *,int,int);
int i,j;
static int adj[6][4]={{2,4,-1,-1},{2,5,-1,-1},{0,1,3,5},
{2,4,-1,-1},{0,3,-1,-1},{1,2,-1,-1}};
struct edge *p,*q;
clrscr();
for(i=0;i<6;i++)
{
g1.reach[i]=0;
g1.nodeno[i]=i;
g1.data[i]='A'+i;
}
for(i=0;i<6;i++)
for (j=0;j<4; j++)
if (adj [i] [j] !=-1)
{
q=(struct edge *)malloc(sizeof(struct edge));
q->destin=adj[i][j];
q->edgeptr=NULL;
if (j==0)
g1.listptr[i]=p=q;
else
{
p->edgeptr=q;
p=q;
}
}
bfs(&g1,0,6);
for(i=0;i<6;i++)
printf("%c\t%d\n",g1.data[i],g1.dist[i]);
getch();
}

void bfs(struct graph *g,int index,int n)
{
void qinsert(int *,int *,int *,int,int);
int qdelete(int *,int *,int *);
int *f,*b;
struct edge *link;
int q[6];
g->reach[index]=1;
g->dist[index]=0;
*f=*b=0;
qinsert(q,f,b,n,index);
while(*b !=0 )
{
index=qdelete(q,f,b);
link=g->listptr[index];
while(link!=NULL)
{
if(!(g->reach[link->destin]))
{
g->dist[link->destin]=g->dist[index]+1;
g->reach[link->destin]=1;
qinsert(q,f,b,n,link->destin);
}
link=link->edgeptr;
}
}
}

void qinsert(int *q,int *f,int *b,int n,int index)
{
if (*b==n)
printf( "queue full\n") ;
else
{
*b=*b+1;
q[*b]=index;
if (*f==0)
*f=*f+1;
}
}

int qdelete(int *q,int *f,int *b)
{
int y;
if(*b==0)
{
printf ( "queue empty\n");
return -1;
}
else
{
y=q[*f];
if (*f==*b)
*f=*b=0;
else
*f=*f+1;
return y;
}
}