Graph

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

 

class node{
private:
char vname;
node *next;
public:
node(char c){ //constructor
vname=c;
next=NULL;
}
node(void){ //overloaded constructor
vname=0;
next=NULL;
}
friend class graph;
};

 

class graph{
private:
int nnodes;
node *vertex;
int *visited;
void dfsvis(int); //depth first search on the adjacency list starting from vertex i
int index(char c); //retiurns the index of a node labelled c.
public:
graph(){ //constructor
cout<<"Creating the graph...\nEnter the number of nodes...";
cin>>nnodes;
visited=(int*)calloc(nnodes,sizeof(int));
vertex=new node[nnodes];
}
void showadjlist(void);
void makeadjlist(void);
void DFS(void);
void BFS(void);
~graph(); //destructor
};

 

//-------------- EXPLICIT FUNCTION DEFINITIONS --------------------------------------

void graph::showadjlist(void){
int i;
node *p;
cout<<"\n\nThe adjacency list...\n\n";
for(i=0;i<nnodes;i++){
cout<<"("<<visited[i]<<")"<<i+1<<".VERTEX:"<<vertex[i].vname;
p=vertex[i].next;
while(p!=NULL){
cout<<"-->"<<p->vname;
p=p->next;
}
cout<<endl;
}
cout<<endl<<endl;
return;
}

 

 

void graph::makeadjlist(void){
int i;
char c1,ans='y';
node *p,*q;
for(i=0;i<nnodes;i++){
showadjlist();
cout<<"\t NODE "<<i+1<<":\n";
cout<<"\tlabel(char): ";
c1=getche();
vertex[i].vname=c1;
p=&vertex[i];
ans='y';
while(ans=='y'&& nnodes>1){
showadjlist();
cout<<"\n\tNODE "<<i+1<<":\n";
cout<<"\tADDITION OF ADJACENT NODES:\n";
cout<<"\n\t\tEnter adjacent node label: ";
c1=getche();
q=new node;
q->vname=c1;
p->next=q;
p=q;
cout<<"\n\tAdd more adjacent nodes?('y'to continue) ";
ans=getche();
}

}
}

int graph::index(char c){
int i,found=0;
for(i=0;i<nnodes;i++)
if(vertex[i].vname==c){
found=1;
break;
}
if(found==0){
cout<<"No such label exists.\n";
return -1;
}

return i;
}

 

void graph::DFS(void){
char cstart;
int i;

cout<<"Enter the label of the start node...";
cin>>cstart;
for(i=0;i<nnodes;i++)//mark all nodes as not visited.
visited[i]=0;
i=index(cstart);
if(i==-1)
cout<<"No such label exists.\n";
else
dfsvis(i);
return;
}

 

void graph::dfsvis(int n){
node *p;
int n1;
visited[n]=1;
cout<<"node "<<n+1<<" visited(label "<<vertex[n].vname<<")\n";
p=vertex[n].next;
while(p!=NULL){
for(n1=0;n1<nnodes;n1++)
if(vertex[n1].vname==p->vname)
break;
if(visited[n1]==0)
dfsvis(n1);
p=p->next;
}
return;
}

 

void graph::BFS(void){
int Q[40],front=0,rear=0;
int i,j;
char c1;
node *p;

cout<<"Enter the starting node label for the breadth first search.\n";
cin>>c1;
for(i=0;i<nnodes;i++)//mark all the nodes as not visited.
visited[i]=0;
i=index(c1); //find index of the entered node.
visited[i]=1;
cout<<"node "<<i+1<<": visited (label:"<<vertex[i].vname<<" )\n";
for(j=0;j<40;j++) //initialize queue
Q[j]=0;
while(1){
p=vertex[i].next;
while(p!=NULL){
j=index(p->vname);
if(visited[j]==0){
Q[rear++]=j;
visited[j]=1;
cout<<"node "<<j+1<<": visited (label:"<<vertex[j].vname<<" )\n";
}
p=p->next;
}
if(rear!=front)
i=Q[front++];
else
break;
}
return;
}

graph::~graph(){
node *p,*q;
int i;

for(i=0;i<nnodes;i++){
p=vertex[i].next;
while(p!=NULL){
q=p;
p=p->next;
delete q;
}
}
delete []vertex;
}

 

 

 

int main(void){
graph g;
g.makeadjlist();
g.showadjlist();
g.DFS();
g.BFS();

return 0;
}