C Program to implement Breadth First Search (BFS) Using Adjacency List (linked list)

PROGRAM : 

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<process.h>
#include<math.h>
typedef struct adja
{
    int data;
    struct adja * link;
    char ch;
    int h;

} adja;

void graph_display(adja arr[],int n);

int front=0;
int rear=-1;

adja *head=NULL,*ptr=NULL;


void graph_bfs_dis(adja arr[],int queue[])
{
    int i,height,level,j;
    level=0;
    for(i=0;i<=rear;i++)
    {
        printf(" -> v(%d)", queue[i] );
    }
    printf("\n\n");

   /* height = (int)(log(rear+1)/log(2));
printf("\n");
    rear=rear+1;
for(i=0; i<rear; i++)
{
if(level!=(int)(log(i+1)/log(2)))
{
printf("\n\n");
level = (int)(log(i+1)/log(2));
}
for(j=(int)pow(2,height-level); j>0; j--)
printf("\t");
printf("%d", queue[i]);

for(j=(int)pow(2,height-level);j>0;j--)
printf("\t");
}
rear=rear-1;*/


}

void set_colour(adja arr[],int queue[],int n)
{
    int i,k,j=rear,d;
    for(i=0;i<n;i++)
    {
        for(k=0;k<=j;k++)
        {
            if(arr[i].data==queue[k])
            {
                    arr[i].ch='b';
            }
        }
        ptr=arr[i].link;
        while(ptr!=NULL)
        {
            for(k=0;k<=j;k++)
            {
                if(ptr->data==queue[k])
                {
                        ptr->ch='b';
                }
            }
            ptr=ptr->link;
        }

    }

}

void graph_bfs(adja arr[],int n)
{
    int queue[n],j,p=0,i=0;
    for(j=0;j<n;j++)
    {
            queue[j]='0';
    }
    do
    {
        head=NULL;
        ptr=NULL;
        if(arr[i].ch=='r')
        {
            rear++;
            queue[rear]=arr[i].data;

        }
        ptr=arr[i].link;
        while(ptr!=NULL)
            {
                if(ptr->ch=='r')
                {
                    queue[++rear]=ptr->data;
                }
                ptr=ptr->link;
            }
            set_colour(arr,queue,n);
            printf("\n     after update ");
            graph_display(arr,n);
            printf("\n visited node ");
            graph_bfs_dis(arr,queue);
            j=queue[++front];
            for(p=0;p<n;p++)
            {
                if(arr[p].data==j)
                {
                    i=p;
                }
            }

    }while((rear+1)<n);
    printf("\n---- after BFS the ordered values and hight are ---  ");
    graph_bfs_dis(arr,queue);
}

void graph_display(adja arr[],int n)
{
    int i;
    printf("the adjacency list is   \n\n ");
    for(i=0;i<n;i++)
    {
        head=NULL;
        ptr=NULL;
        printf(" %d(%c)",(arr[i].data),(arr[i].ch));
        ptr=arr[i].link;

        while(ptr!=NULL)
        {
            printf("->%d(%c)",ptr->data,ptr->ch);
            ptr=ptr->link;
        }

        printf("\n \n ");
    }

}

void graph_input(int n,adja arr[])
{

    int i,j,m,p;
    for(i=0;i<n;i++)
    {
        head=NULL;
        ptr=NULL;

        printf("\n enter the value  of number %d vertex ",(i+1));
        scanf("%d",&(arr[i].data));
        arr[i].ch='r';
        arr[i].h=-99;
        arr[i].link=NULL;
        if(n>1)
        {
            printf("\n enter the number of vertices connected with %d ",(arr[i].data));
        scanf("%d",&p);

        if(p!=0)
        {
            printf("\n enter the value of  vertices connected  with %d  ",(arr[i].data));

            for(j=0;j<p;j++)
            {
                scanf("%d",&m);
                ptr=(adja *)malloc(sizeof(adja));
                ptr->data=m;
                ptr->ch='r';
                ptr->link=NULL;
                ptr->h=-99;

                if(j==0)
                {
                    arr[i].link=ptr;
                    //printf(" %d ",arr[i].data);
                }
                else
                {
                    head->link=ptr;
                }
                head=ptr;

            }
        }


        }

    }

}

int main()
{
    int n,i,j,m,p;

    printf("\n enter the number of vertex ");
    scanf("%d",&n);
    if(n!=0)
        {
            adja *arr=(adja *)malloc(n*sizeof(adja));

                graph_input(n,arr);

                arr[0].h=0;

                printf("\n======================================================================================\n");

                printf("\n     initial situation of ");

                graph_display(arr,n);

                printf("\n      root node of tree is  [%d] \n",arr[0].data);

                graph_bfs(arr,n);
        }
    else
            {
                printf("\n graph is empty \n");
            }

}

OUTPUT :