//THIS SOURCE CODE WAS PROGRAMMED BY O.R.SENTHIL KUMARAN
//GRAPH TRAVERSAL
#include"stdio.h"
#include"malloc.h"
#define TRUE 1
#define FALSE 0
int i,n,m[10][10],j;
struct node
{
 int data;
 int visited;
 char str[30];
}*a[50];
df_search()
{
 for(i=0;i<n;i++)
 a[i]->visited=FALSE;
 for(i=0;i<n;i++)
 {
  if(!a[i]->visited)
  {
   search_from(i);
  }
 }
 return 0;
}
search_from(int k)
{
 int j;
 a[k]->visited=TRUE;
 strcpy(a[k]->str,"VISITED");
 printf("\t%d",a[k]->data);
 for(j=0;j<n;j++)
 {
  if((!a[j]->visited)&&(m[k][j]!=0))
  search_from(j);
 }
return 0;
}
bf_search()
{
 int i,j,b[50];
 for(i=0;i<n;i++)
 {
  for(j=0;j<n;j++)
  {
   b[j]=0;
   if(m[i][j]==1||m[0][0]==0)
    {
     if(b[j]!=1)
     {
      b[j]=1;
      m[0][0]=1;
      printf("\t%d",a[j]->data);
      strcpy(a[j]->str,"VISITED");
     }
    }
   }
  }
  return 0;
}
getdata()
{
 printf("\nENTER THE NUMBER OF NODES");
 scanf("%d",&n);
 for(i=0;i<n;i++)
 {
  clrscr();
  printf("\nENTER THE DATA FOR THE NODE");
  fflush(stdin);
  printf("\n\tNODE %d",i+1);
  a[i]=(struct node *)malloc(sizeof(struct node));
  scanf("%d",&a[i]->data);
  for(j=0;j<n;j++)
   {
   printf("\nENTER THEVALUE OF THE ADJECENCY MATRIX 1 OR 0\t");
   fflush(stdin);
   scanf("%d",&m[i][j]);
    }
  }
}
void main()
{
 int ch;
 clrscr();
 getdata();
 do
 {
 printf("\n\tGRAPH TRAVERSAL");
 printf("\n1.DEPTH FIRST SEARCH\n");
 printf("\n2.BREADTH FIRST SEARCH\n");
 printf("\n3.DISPLAY");
 printf("\n4.EXIT");
 printf("\nENTER YOUR CHOICE");
 fflush(stdin);
 scanf("%d",&ch);
 switch(ch)
 {
 case 1:
	df_search();
	break;
 case 2:
	bf_search();
	break;
 case 3:
	display();
	break;
 case 4:
	exit();
	break;
 default:
	 printf("\nINVALID CHOICE");
	 break;
 }
}while(ch!=4);
}

display()
{
 int i;
 for(i=0;i<n;i++)
 {
  printf("\nDATA: %d",a[i]->data);
  printf("\n %s",a[i]->str);
 }
 return 0;
}