#include<stdio.h>
#include<stdlib.h>
#define MAX_NODES 20
typedef struct node
{
int nodenum;
struct node *adj;
}graphnode;
int main()
{
int no_of_nodes,i,j,nodeno,start_node,head=1,tail=1,dis;
int adj_nodes,d[MAX_NODES];
char color[MAX_NODES];
graphnode *queue[MAX_NODES];
graphnode *arr[MAX_NODES];
graphnode *n=NULL;
graphnode *p=NULL;
graphnode *q=NULL;
printf("enter the number of nodes");
scanf("%d",&no_of_nodes);
if(!(no_of_nodes<=MAX_NODES))
{
printf("tree can not be formed");
exit(0);
}
for(i=1;i<=no_of_nodes;i++)
{
printf("enter no. of nodes which are adjacent to %d :",i);
scanf("%d",&adj_nodes);
arr[i]=(graphnode *)malloc(sizeof(graphnode));
arr[i]->nodenum=i;
arr[i]->adj=NULL;
for(j=1;j<=adj_nodes;j++)
{
printf("enter the adjacent node :");
scanf("%d",&nodeno);
n=(graphnode *)malloc(sizeof(graphnode));
n->nodenum=nodeno;
n->adj=NULL;
p=arr[i];
while(p->adj!=NULL)
{
p=p->adj;
}
p->adj=n;
}
}
/*for(i=1;i<=no_of_nodes;i++)
{
printf("\n Node number %d", arr[i]->nodenum);
printf("\n adjacent nodes \n");
p=arr[i]->adj;
while(p!=NULL)
{
printf("\n adjacenbt node number %d",p->nodenum);
p=p->adj;
}
}*/
printf("\nEnter the node number of the starting vertex");
scanf("%d",&start_node);
d[start_node]=0;
color[start_node]='g';
for(i=1;i<=no_of_nodes;i++)
{
if(i!=start_node)
{
color[i]='w';
d[i]=no_of_nodes + 1;
}
}
queue[tail]=arr[start_node];
head=tail;
tail++;
while(tail!=head)
{
p=queue[head];
//printf("\nqueue head : %d",queue[head]->nodenum);
i=(queue[head]->nodenum);
++head;
q=arr[i];
p=q;
dis=d[p->nodenum];
while(p->adj!=NULL)
{
//n=(graphnode *) malloc(sizeof(graphnode));
n=p->adj;
if(color[n->nodenum]=='w')
{
//printf("parent %d\n",p->nodenum);
//printf("adjacent %d\n",n->nodenum);
color[n->nodenum]='g';
d[n->nodenum]=dis+1;
queue[tail]=n;
tail++;
}
p=p->adj;
}
color[q->nodenum]='b';
}
printf("color and distance vectors for each node are as \n");
for(i=1;i<=no_of_nodes;i++)
{
printf("for node %d distance is %d color is %c \n",i,d[i],color[i]);
}
return 1;
}