on Depth First Search and Breadth First Search
Some Errors are there please clear if it is possible
Program
Code:
#include<iostream.h>
#include<conio.h>
#define true 1
#define false 0
class node
{
int data; //each node contain adjancent vertex
node *link;
friend class graph;
};
class graph //we can use data link in graph class
{
private:
int n; //vertex
int e; //edge
sll<int> *a; //array of sll objects vertex num are integer
public:
graph(); //initialise n,e
~graph(); //delete all the linked list in the array
void create(); // create all the linked list
void display(); // display all the linked list
int degree(int i); //return the depth of ith vertex
void bft();
void dft();
void traverse(int j,int * visited);
void nov(); //return no of vertex
void noe(); //return no of edges
};
graph::graph()
{
cout<<"Enter the no of vertex\n";
cin>>n;
cout<<"Enter the no of edges of graph\n";
cin>>e;
a=new sll<int>[n];
}
void graph::create()
{
for(int i=0;i<=n-1;i++)
{
cout<<"Enter adjancent vertices of "<<i<<"in ascending order terminated -1"<<"\n";
a[i].create();
}
}
int graph::degree(int i)
{
return(a[i].length())
}
int graph::nov()
{
return(n);
}
int graph::noe()
{
return(e);
}
graph::~graph()
{
for(int i=0;i<n-1;i++)
a[i].erase();
delete[] a;
}
void graph::display()
{
for(int i=0;i<n-1;i++)
a[i].display(i);
}
template<class t>void sll<t>::display()
{
node *temp;
temp=first;
if(first==NULL)
cout<<" Adjancent \n";
else
while(temp!=NULL)
{
cout<<temp->data;
temp=temp->link;
}
}
void graph::bft()
{
node *temp;
int i,j;
queue<int> b;
int *visited;
visited =new int[n];
for(int i=0;i<n-1;i++)
visited[i]=false;
for(int i=0;i<=n-1;i++)
{
if(!visted[i])
{
b.insert(i);
while(!b.isempty())
{
j=b.del();
if(!visited[j])
{
cout<<j;
visited[j]=false;
for(temp=a[j].first;temp!=NULL;temp=temp->link)
{
if(!visited[temp->data])
b.insert(temp->data);
}
}
}
}
}
}
void graph::dft()
{
int *visited;int i;
visited=new int[n];
for(i=0;i<=n-1;i++)
visited[i]=false;
for(i=0;i<n-1;i++)
{
if(!visited[i])
traverse(i,visited);
}
}
void graph::travrse(int j,int visited[])
{
if(visited[j])
{
cout<<j;
visited[j]=true;
for(temp=a[j].first;temp!=NULL;temp=temp->link)
{
if(!visited[temp->data])
traverse(temp->data,visited);
}
}
}
void menu()
{
cout<<"1.Print the Graph\n";
cout<<"2.Display no of vertices and edges\n";
cout<<"3.Display Degree of each vertex\n";
cout<<"4.BFT\n";
cout<<"5.DFT\n";
cout<<"Exit\n";
}
main()
{
int ch;
graph a;
a.create();
menu();
cout<<"Enter Your Choice\n";
cin>>ch;
while(ch<6)
{
switch(ch)
{
case 1:
a.display();
break;
case 2:
cout<<"No of vertices :"<<a.nov();<<"\n";
cout<<"No of edges :"<<a.noe();<<"\n";
break;
case 3:
for(int i=0;i<=a.nov()-1;i++)
cout<<i<<"\t"<<a.degree(i)<<"\n";
break;
case 4:
a.bft();
cout<<"\n";
break;
case 5:
a.dft();
cout<<"\n";
break;
}
menu();
cout<<"Enter Your Choice\n";
cin>>ch;
}
getch();
return(0);
}
