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

#define MAX 50
/*
Program to Implement Depth First Search for Graphs using Recursion
and Breadth First Search for Graphs using Non-Recursive Function
This is Practical for B.Sc., Comp. Sci.
*/
int adj[MAX][MAX];

class graph
{
private:
int vx[MAX];
int vd[MAX];

public:
graph()
{
}
~graph()
{
}
void creategraph(int);
void df(int);
void bf(int);
void dfs(int,int);
};

void graph::dfs(int ad,int v)
{
int k,flag;
for(k=ad;k<v;k++)
for(int j=0;j<v;j++)
if(adj[k][j]==1)
{
if(vd[j]==0)
{
vd[j]=1;
cout<<vx[j]<<" ==>> ";
dfs(j,v);
}
}
}

void graph::creategraph(int v)
{
int i,j;
for(i=0;i<v;i++)
{
cout<<"\nEnter the Node Value :";
cin>>vx[i];
vd[i]=0;
}
for(i=0;i<v;i++)
for(j=0;j<v;j++)
adj[i][j]=0;
cout<<"Enter the Adjacency Vertices List for each Vertex of the Graph:"<<endl;
int n,m,k;

for(i=0;i<v;i++)
{
cout<<"Enter the No.of Adjacency Vertices for Vertex "<<vx[i]<<" : ";
cin>>n;

for(j=1;j<=n;j++)
{
cout<<"Enter the Adjacency Vertex : ";
cin>>m;
for(k=0;k<v;k++)
{
if(vx[k]==m)
adj[i][k]=1;
}
}
}
clrscr();
cout<<"\nGraph Created with No.of Vertices : "<<v<<endl<<endl;

cout<<"\nThe Adjacency Matrix of the Graph is :\n\n";
for(i=0;i<v;i++)
{
for(j=0;j<v;j++)
cout<<adj[i][j]<<" ";
cout<<endl;
}
}
void graph::df(int v)
{
int i=0;
for(i=0;i<v;i++)
vd[i]=0;
adj[0][0]=1;
vd[0]=1;

cout<<"\t\t\tDepth First Traversal\n\n";
cout<<vx[0]<<" ==>> ";
dfs(0,v);
}
void graph::bf(int v)
{
int i,j;
for(i=0;i<v;i++)
vd[i]=0;

cout<<"\t\t\tBreadth First Traversal\n\n";
cout<<vx[0]<<" ==>> ";
vd[0]=1;
for(i=0;i<v;i++)
{
for(j=0;j<v;j++)
{
if(adj[i][j]==1)
{
if(vd[j]==0)
{
cout<<vx[j]<<" ==>> ";
vd[j]=1;
}
}
}
}
cout<<" X \n\n";
}

void main()
{
graph g;
int ch,v;
do
{
clrscr();
cout<<"\t\t\tGraph Creation and Traversal\n\n";
cout<<"\t1.Create Graph \n";
cout<<"\t2.Breadth Fisrt Traversal\n";
cout<<"\t3.Depth Fisrt Traversal\n";
cout<<"\t4.Quit\n\n\n";

cout<<"\tEnter Your Choice [ 1 - 4 ] : ";
cin>>ch;
switch(ch)
{
case 1:
{
clrscr();
cout<<"\t\t\tGraph Creation\n\n";
cout<<"Enter the Number of Vertices to be Created :";
cin>>v;
g.creategraph(v);
cout<<"Press Any Key to Continue . . . ";
getch();
break;
}
case 2:
{
clrscr();
g.bf(v);
cout<<"Press Any Key to Continue . . . ";
getch();
break;
}
case 3:
{
clrscr();
g.df(v);
cout<<" X \n\n";
cout<<"Press Any Key to Continue . . . ";
getch();
break;
}
case 4:
cout<<"Bye ...";
break;
}
}
while(ch!=4);
}