#include<iostream.h>
#include<conio.h>

#define MAX 20
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define INFINITY 999999
#define NIL -1
int *queue , rear;
int adjMatrix[MAX][MAX];
void enqueue(int data)
{
    queue[rear++] = data;
}

int dequeue(void )
{
    int data = queue[0];
    if(rear>1)
         for(int i = 0;i<rear-1;i++)
              queue[i] = queue[i+1];
    rear--;
    return data;
}
struct node
{
     char name;
     int d;
     int pi;
     int color;
};  
int findAdj(int *adj , int index , int n)
{
     int count =  0;
     for(int i=0;i<n;i++)
     {
          if(adjMatrix[index][i] == 1)
          {
               adj[count++] = i;
          
          }
     }
     return count;
}
void logic(struct node *vertex,int n)
{
      int *adjacent , noOfAdjacent , i;
      int currentVertex;
      adjacent = new int[n];
      enqueue(0);
      cout<<"\n\nThe BFS result is : \n\n";
      while(rear != 0)
      {
           
           currentVertex = dequeue();
           
           printf(" %c",vertex[currentVertex].name);
           
           noOfAdjacent = findAdj(adjacent , currentVertex , n);
           for(int i=0;i<noOfAdjacent;i++)
           {
                 if(vertex[adjacent[i]].color == WHITE )
                 {
                     vertex[adjacent[i]].color = GRAY;
                     vertex[adjacent[i]].d = vertex[currentVertex].d + 1;
                     vertex[adjacent[i]].pi = currentVertex;
                     enqueue(adjacent[i]);
                 }
                 vertex[currentVertex].color = BLACK;
           }
      }
}      

void getData(struct node *vertex , int n)
{
     int i=0;
     cin>>vertex[0].name;
     for(i=1;i<n;i++)
     {
          cin>>vertex[i].name;
          vertex[i].color=WHITE;
          vertex[i].pi = NIL;
          vertex[i].d =  INFINITY;
     }
     vertex[0].color = GRAY;
     vertex[0].d = 0;
     vertex[0].pi = NIL;
}


int main()
{
     int n,i,j;
     struct node *vertex;
     cout<<"\nEnter the no. of nodes : ";
     cin>>n;
     queue = new int[n];
     vertex = new node[n];
     cout<<"\nEnter the name of nodes(starting from source) : ";
     getData(vertex , n);
     cout<<"\n\nEnter the Values of the Adjacency Matrix(in 0,1) : ";
     for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
            printf("\nPath %c--->%c = ",vertex[i].name,vertex[j].name);
            scanf("%d",&adjMatrix[i][j]);
        }
     
     logic(vertex , n);
     
     getch();
     return 0;
}