#include <stdlib.h>
int q[15]={0},prev[10]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},col[15]={0},s,j,count=0 ;
int front = 0,rear = 0,d[10]={0},black = 2,grey =1,white = 0,in[50][50];
void queue(int val)
{
q[front++] = val;
}
int deque()
{
if(front == rear)
return -1;
return q[rear++];
}
void bfs(int ver)
{
int i,u;
col [s] = grey;
//s is starting vertex
d[s] = 0;
queue(s);
while((u = deque()) != -1)
{
col[u]=grey;
for(i = u,j = 1;j <= ver;j++)
{
if(in[i][j] == 1){//checking if any adjacent of u has an edge with any overtex
if(col[j] == white)
{
col[j] = grey;
prev[j] = i;
d[j] = d[u] + 1;
queue(j);
}
}
}
col[i] = black;
}
}
int main()
{
int i,k,u,v;
int a,b,ver,ed;
FILE *fp;
fp = freopen("input.txt","rt",stdin);
printf("Enter ur vertex num :");
scanf("%d",&ver);
printf("%d\n",ver);
printf("Enter ur edge num :");
scanf("%d",&ed);
printf("%d\n",ed);
printf("Enter your starting point :");
scanf("%d",&s);
printf("%d\n",s);
printf("Enter edge list :\n");
for(i = 1;i <= ed;i++)
{
scanf("%d %d",&a,&b);
in[a][b] = 1;
in[b][a] = 1;
printf("in[%d][%d] = 1\n",a,b);
}
bfs(ver);
for(i = 1;i <= ver;i++){
printf("The distance from source %d to vertex %d is - %d and previous is %d\n",s,i,d[i],prev[i]);
}
return 0;
}
