Graph
#include<iostream.h>
#include<conio.h>
class Queue
{
private:
int *a;//a can point to run time array
int f,r,size;//f,r are subscripts, size is array size
public:
Queue(int k=40);//40 is the default value to the constructor
~Queue();
int isempty();
int isfull();
void insert(int);
int del();
int first();
int last();
void display();
};
Queue::Queue(int k)
{
size=k;//value passed from the fun.call or default value k=40
//initial values
f=0;
r=-1;
a=new int[size];//create an array &base adress is stored in obj
}
Queue::~Queue()
{
delete[] a;//delete that array where a points
}
int Queue::isempty()
{
return(r==-1);
}
int Queue::isfull()
{
return(r==size-1);
}
void Queue::insert(int x)//x is value to be inserted
{
//testing for empty locations on right side of the Queue
if(isfull())
//or if(r==size-1)
cout<<"insertion is not possible\n";
else
{
r++;//move on next location
a[r]=x;//insert x in array a at subscript 'r'
}
}
int Queue::del()
{
int x;
if(isempty())//if q is empty retun(-1)
return(-1);
x=a[f];//copy 1st inserted value to x before it is deleted
f++;//delete 1st inserted value(logically)
if(f>r)//if q is empty after deletion,reinitialize f and r
{
f=0;
r=-1;
}
return(x);//deleted value
}
void Queue::display()
{
if(isempty())
cout<<"Queue is empty\n";
else
{
cout<<"Queue is as follows\n";
for(int i=f;i<=r;i++)//display a[i] where i values from f to r
cout<<a[i]<<"\t";
cout<<"\n";
}
}
int Queue::first()
{
if(isempty())//If Queue is empty return-1
return(-1);
else
return(a[f]);//1st inserted value of the Queue
}
int Queue::last()
{
if(isempty())//if Queue is empty return -1
return(-1);
else
return(a[r]);//last inserted value of the Queue
}
void menu()
{
cout<<"1.insertion\n";
cout<<"2. deletion\n";
cout<<"3. display Queue\n";
cout<<"3.1st inserted value\n";
cout<<"4.1st inserted value\n";
cout<<"5.last inserted value\n";
cout<<"6.exit\n";
}
/*void main()
{
int ch,k,x;
void menu();
cout<<"enter size of the Queue\n";
cin>>x;
Queue Q(k);
clrscr();
menu();
cout<<"enter ur choice\n";
cin>>ch;
while(ch<6)
{
switch(ch)
{
case 1:{
cout<<"enter value to be inserted\n";
cin>>x;
if(x==-1)
cout<<"Invalid no\n";
else
Q.insert(x);
break;
}//case
case 2:{
x=Q.del();
if(x==-1)
cout<<"Queue is empty,del is not possible\n";
else
cout<<"deleted value="<<x<<"\n";
break;
} //case
case 3:{
Q.display();
break;
} //case
case 4:{
x=Q.first();//function returns 1st inserted value
if(x==-1)
cout<<"Queue is empty\n";
else
cout<<"First insert value is"<<x<<"\n";
break;
}//case
case 5:{
x=Q.last();//function returns last inserted value
if(x==-1)
cout<<"Queue is empty\n";
else
cout<<"last insert value is"<<x<<"\n";
break;
}//case
}//switch
menu();
cout<<"enter ur choice\n";
cin>>ch;
}//while
} //main()*/
class Node
{
private:
int data;
Node *link;
friend class sll;
};
class sll
{
private:
Node *first;
public:
sll();
~sll();
int isempty();
void display();
int length();
void erase();
void insert(int i, int x);
int del(int i);
int find(int i);
Node *search(int x);
sll(sll &a);//cc
void create();
void append(Node *k);
void reverse();
};
sll::sll()
{
first=NULL;
}
int sll::isempty()
{
return(first==NULL);
}
void sll::display()
{
Node *p;//p is a pointer to a //node
if(isempty())
cout<<"Linked list is empty\n";
else
{
cout<<"Linked List is as follows\n";
for(p=first;p!=NULL;p=p->link)
cout<<p->data<<"\t"<<p->link<<"\n";
}
}
int sll::length()
{
Node *p;//p is a pointer to ode
int ctr=0;
p=first;
while(p!=NULL)/*cnt each node in the linked list*/
{
ctr++;
p=p->link;
}//while
return(ctr);
}
int sll::find(int i)
{
Node *p;
if(i<1||i>length())//i must be //b/w 1 and length
return(-1);//ith node does //not exist
p=first;
for(int j=1;j<=i-1;j++)
p=p->link;
return(p->data);//ith node //data
}
Node* sll::search(int x)
{
Node *p=first;
while(p!=NULL)
{
if(p->data==x)
return(p);
else
p=p->link;
}
return(NULL);
}
/*k is a ptr to new node to be appended*/
void sll::append(Node *k)
{
Node *last;//last is a ptr to //Node
k->link=NULL;
if(isempty())
first=k;
else
{
last=first;
while(last->link!=NULL)
last=last->link;
last->link=k;/*attach last node and the new node k */
}
}
void sll::create()
{
int x;
Node *k;
first=NULL;//initially Linked //list is empty
cout<<"enter values terminated by -1 (or)!\n";
cin>>x;
while(x!=-1&&x!='!')
{
k=new Node;
k->data=x;
append(k);
cin>>x;
}
}
sll::sll(sll &a)
{
Node *p,*k;
first=NULL;
p=a.first;
while(p!=NULL)
{
k=new Node;
k->data=p->data;
append(k);
p=p->link;
}
}
void sll::erase()
{
Node *p;
while(!isempty())
{
p=first;
first=first->link;
delete p;
}
}
sll::~sll()
{
erase();
}
void sll::reverse()
{
Node *cur,*prev,*next;
next=first;
cur=NULL;
while(next!=NULL)
{
prev=cur;
cur=next;
next=next->link;
cur->link=prev;
}
first=cur;
}
void sll::insert(int i, int x)
{
Node *p,*temp;
if(i<0||i>length())
cout<<"Non-existing Node\n";
else
{
p=new Node;
p->data=x;
if(i==0)
{
p->link=first;
first=p;
}
else
{
temp=first;
for(int j=1;j<=i-1;j++)
temp=temp->link;
p->link=temp->link;
temp->link=p;
}
}
}
int sll::del(int i)
{
Node *p,*pres,*prev;
int x;
if(i<1||i>length())
return(-1);
else if(i==1)
{
p=first;
first=first->link;
x=p->data;
delete p;
return(x);
}
else
{
pres=first;
for(int j=1;j<=i-1;j++)
{
prev=pres;
pres=pres->link;
}
prev->link=pres->link;
x=pres->data;
delete pres;
return(x);
}
}
class graph
{
private:
int n;//no of vertices in the //graph
sll *a;//a is ptr to array of object
public:
void create();
int nov();
int noe();
int degree(int i);
void bfs();
void dfs();
void traverse(int i,int *visited);
~graph();
void display();
};
void graph::create()
{
cout<<"enter no of vertices\n";
cin>>n;
//create array of n objects, a is ptr to array, sll contructor is called n times
a=new sll[n];
for(int i=0;i<=n-1;i++)
{
cout<<"Enter adjacent vertex"<<i<<"in ascending terminated by -1\n";
a[i].create();
}
}
void graph::display()
{
for(int i=0;i<=n-1;i++)
{
cout<<"Adj vertices of vertex"<<i<<":";
a[i].display();
}
}
/*void sll::display()
{
Node *p;
if(isempty())
cout<<"No of Adj.vertices\n";
else
{
for(p=first;p!=NULL;p=p->link)
cout<<p->data<<"\t";
cout<<"\n";
}
} */
int graph::degree(int i)
{
return(a[i].length());
}
void graph::bfs()
{
Node *p;
int i,*visited;
Queue q;//constructor is called
visited=new int[n];
for(i=0;i<=n-1;i++)//initially none of the vertices are visited
visited[i]=false;//initially array with false
for(i=0;i<=n-1;i++)//This is necessary in view of directed end disconnected graph
{
if(!visited[i])//if ith vertex is not visited,insert into the queue, i is starting //vertex
{
q.insert(i);
do
{
j=q.del();//delete a vertex from the queue
if(!visited[j])//jth vertex is not visited,display j
{
Node*p;
cout<<j;
visited[j]=true;//jth vertex is visited
//process adjacent vertices of jth vertex
for(p=a[j].first;p!=NULL;p=p->link;)
{
//if the adjacent vertices is not visited, insert into the Queue
if(!visited[p->data])
q.insert(p->data);
}//for
}//if
}
while(!q.isempty());//execute loop untill queue is empty
}//if
}//for
}function
void graph::dfs()
{
int i,*visited;
visited=new int[n];//create of size n;visited is a pointer to it
for(i=0;i<=n-1;i++)//initially non of the vertices are visited
visited[i]=false;//initially array with false,false,false
for(i=0;i<=n-1;i++)//this is necessary in view of directed and disconnected graph
{
if(!visited[i])//if ith vertex is not visited,call the function on vertex i,
//where i is the starting vertex of componant
traverse(i,visited);
}
}
void graph::traverse(int i,int *visited)
{
Node *p;//p is a ptr to node
if(!visited[i])//if ith vertex is not visited,visit it now
{
cout<<i;
visited[i]=true;//mark the ith vertex as visited vertex
//process ith adjacent vertices of ith vertex
for(p=a[i].fist;p!=NULL;p=p->link)
{
if(!visited[p->data])//if adjacent vertex is not visited,
//call the same function on adjacent vertex
traverse(p->data,visited);
}
}
}
void menu()
{
cout<<"1.Display the graph\n";
cout<<"2.No of vertices &edges of graph\n";
cout<<"3.Degree of each vertex in the graph\n";
cout<<"4.Bread First Search \n";
cout<<"5.Dfs\n";
cout<<"6.exit\n";
}
void main()
{
graph g;//vertices
int ch;
g.create();//create a graph whose address is stored in object g
clrscr();
menu();
count<<"enter your choice\n";
cin>>ch;
while(ch<6)
{
switch(ch)
{
case 1:{
g.display();
break;
}//case
case 2:{
//nov() returns no of vertices and edges
cout<<"No of vertices are="<<g.nov()<<"\n";
cout<<"No. edges="<<g.noe()<<"\n";
break;
}//case 2
case 3:
{
//i is the vertex no, degree of i is the degree of i is the
//degree of ith vertex, where i varies from 0 to no.of (vertices-1)
cout<<i<<"\t"<<g.degree(i)<<"\n";
break;
}
case 4:
{
g.bfs();//visit the graph in bfs
cout<<"\n";
break;
}
case 5:
{
g.dfs();//visit the graph in dfs
cout<<"\n";
break;
}
} //switch
menu();
cout<<"enter your choice\n";
cin>>ch;
}//while
getch();
}//main()
#include<iostream.h>
#include<conio.h>
class Queue
{
private:
int *a;//a can point to run time array
int f,r,size;//f,r are subscripts, size is array size
public:
Queue(int k=40);//40 is the default value to the constructor
~Queue();
int isempty();
int isfull();
void insert(int);
int del();
int first();
int last();
void display();
};
Queue::Queue(int k)
{
size=k;//value passed from the fun.call or default value k=40
//initial values
f=0;
r=-1;
a=new int[size];//create an array &base adress is stored in obj
}
Queue::~Queue()
{
delete[] a;//delete that array where a points
}
int Queue::isempty()
{
return(r==-1);
}
int Queue::isfull()
{
return(r==size-1);
}
void Queue::insert(int x)//x is value to be inserted
{
//testing for empty locations on right side of the Queue
if(isfull())
//or if(r==size-1)
cout<<"insertion is not possible\n";
else
{
r++;//move on next location
a[r]=x;//insert x in array a at subscript 'r'
}
}
int Queue::del()
{
int x;
if(isempty())//if q is empty retun(-1)
return(-1);
x=a[f];//copy 1st inserted value to x before it is deleted
f++;//delete 1st inserted value(logically)
if(f>r)//if q is empty after deletion,reinitialize f and r
{
f=0;
r=-1;
}
return(x);//deleted value
}
void Queue::display()
{
if(isempty())
cout<<"Queue is empty\n";
else
{
cout<<"Queue is as follows\n";
for(int i=f;i<=r;i++)//display a[i] where i values from f to r
cout<<a[i]<<"\t";
cout<<"\n";
}
}
int Queue::first()
{
if(isempty())//If Queue is empty return-1
return(-1);
else
return(a[f]);//1st inserted value of the Queue
}
int Queue::last()
{
if(isempty())//if Queue is empty return -1
return(-1);
else
return(a[r]);//last inserted value of the Queue
}
void menu()
{
cout<<"1.insertion\n";
cout<<"2. deletion\n";
cout<<"3. display Queue\n";
cout<<"3.1st inserted value\n";
cout<<"4.1st inserted value\n";
cout<<"5.last inserted value\n";
cout<<"6.exit\n";
}
/*void main()
{
int ch,k,x;
void menu();
cout<<"enter size of the Queue\n";
cin>>x;
Queue Q(k);
clrscr();
menu();
cout<<"enter ur choice\n";
cin>>ch;
while(ch<6)
{
switch(ch)
{
case 1:{
cout<<"enter value to be inserted\n";
cin>>x;
if(x==-1)
cout<<"Invalid no\n";
else
Q.insert(x);
break;
}//case
case 2:{
x=Q.del();
if(x==-1)
cout<<"Queue is empty,del is not possible\n";
else
cout<<"deleted value="<<x<<"\n";
break;
} //case
case 3:{
Q.display();
break;
} //case
case 4:{
x=Q.first();//function returns 1st inserted value
if(x==-1)
cout<<"Queue is empty\n";
else
cout<<"First insert value is"<<x<<"\n";
break;
}//case
case 5:{
x=Q.last();//function returns last inserted value
if(x==-1)
cout<<"Queue is empty\n";
else
cout<<"last insert value is"<<x<<"\n";
break;
}//case
}//switch
menu();
cout<<"enter ur choice\n";
cin>>ch;
}//while
} //main()*/
class Node
{
private:
int data;
Node *link;
friend class sll;
};
class sll
{
private:
Node *first;
public:
sll();
~sll();
int isempty();
void display();
int length();
void erase();
void insert(int i, int x);
int del(int i);
int find(int i);
Node *search(int x);
sll(sll &a);//cc
void create();
void append(Node *k);
void reverse();
};
sll::sll()
{
first=NULL;
}
int sll::isempty()
{
return(first==NULL);
}
void sll::display()
{
Node *p;//p is a pointer to a //node
if(isempty())
cout<<"Linked list is empty\n";
else
{
cout<<"Linked List is as follows\n";
for(p=first;p!=NULL;p=p->link)
cout<<p->data<<"\t"<<p->link<<"\n";
}
}
int sll::length()
{
Node *p;//p is a pointer to ode
int ctr=0;
p=first;
while(p!=NULL)/*cnt each node in the linked list*/
{
ctr++;
p=p->link;
}//while
return(ctr);
}
int sll::find(int i)
{
Node *p;
if(i<1||i>length())//i must be //b/w 1 and length
return(-1);//ith node does //not exist
p=first;
for(int j=1;j<=i-1;j++)
p=p->link;
return(p->data);//ith node //data
}
Node* sll::search(int x)
{
Node *p=first;
while(p!=NULL)
{
if(p->data==x)
return(p);
else
p=p->link;
}
return(NULL);
}
/*k is a ptr to new node to be appended*/
void sll::append(Node *k)
{
Node *last;//last is a ptr to //Node
k->link=NULL;
if(isempty())
first=k;
else
{
last=first;
while(last->link!=NULL)
last=last->link;
last->link=k;/*attach last node and the new node k */
}
}
void sll::create()
{
int x;
Node *k;
first=NULL;//initially Linked //list is empty
cout<<"enter values terminated by -1 (or)!\n";
cin>>x;
while(x!=-1&&x!='!')
{
k=new Node;
k->data=x;
append(k);
cin>>x;
}
}
sll::sll(sll &a)
{
Node *p,*k;
first=NULL;
p=a.first;
while(p!=NULL)
{
k=new Node;
k->data=p->data;
append(k);
p=p->link;
}
}
void sll::erase()
{
Node *p;
while(!isempty())
{
p=first;
first=first->link;
delete p;
}
}
sll::~sll()
{
erase();
}
void sll::reverse()
{
Node *cur,*prev,*next;
next=first;
cur=NULL;
while(next!=NULL)
{
prev=cur;
cur=next;
next=next->link;
cur->link=prev;
}
first=cur;
}
void sll::insert(int i, int x)
{
Node *p,*temp;
if(i<0||i>length())
cout<<"Non-existing Node\n";
else
{
p=new Node;
p->data=x;
if(i==0)
{
p->link=first;
first=p;
}
else
{
temp=first;
for(int j=1;j<=i-1;j++)
temp=temp->link;
p->link=temp->link;
temp->link=p;
}
}
}
int sll::del(int i)
{
Node *p,*pres,*prev;
int x;
if(i<1||i>length())
return(-1);
else if(i==1)
{
p=first;
first=first->link;
x=p->data;
delete p;
return(x);
}
else
{
pres=first;
for(int j=1;j<=i-1;j++)
{
prev=pres;
pres=pres->link;
}
prev->link=pres->link;
x=pres->data;
delete pres;
return(x);
}
}
class graph
{
private:
int n;//no of vertices in the //graph
sll *a;//a is ptr to array of object
public:
void create();
int nov();
int noe();
int degree(int i);
void bfs();
void dfs();
void traverse(int i,int *visited);
~graph();
void display();
};
void graph::create()
{
cout<<"enter no of vertices\n";
cin>>n;
//create array of n objects, a is ptr to array, sll contructor is called n times
a=new sll[n];
for(int i=0;i<=n-1;i++)
{
cout<<"Enter adjacent vertex"<<i<<"in ascending terminated by -1\n";
a[i].create();
}
}
void graph::display()
{
for(int i=0;i<=n-1;i++)
{
cout<<"Adj vertices of vertex"<<i<<":";
a[i].display();
}
}
/*void sll::display()
{
Node *p;
if(isempty())
cout<<"No of Adj.vertices\n";
else
{
for(p=first;p!=NULL;p=p->link)
cout<<p->data<<"\t";
cout<<"\n";
}
} */
int graph::degree(int i)
{
return(a[i].length());
}
void graph::bfs()
{
Node *p;
int i,*visited;
Queue q;//constructor is called
visited=new int[n];
for(i=0;i<=n-1;i++)//initially none of the vertices are visited
visited[i]=false;//initially array with false
for(i=0;i<=n-1;i++)//This is necessary in view of directed end disconnected graph
{
if(!visited[i])//if ith vertex is not visited,insert into the queue, i is starting //vertex
{
q.insert(i);
do
{
j=q.del();//delete a vertex from the queue
if(!visited[j])//jth vertex is not visited,display j
{
Node*p;
cout<<j;
visited[j]=true;//jth vertex is visited
//process adjacent vertices of jth vertex
for(p=a[j].first;p!=NULL;p=p->link;)
{
//if the adjacent vertices is not visited, insert into the Queue
if(!visited[p->data])
q.insert(p->data);
}//for
}//if
}
while(!q.isempty());//execute loop untill queue is empty
}//if
}//for
}function
void graph::dfs()
{
int i,*visited;
visited=new int[n];//create of size n;visited is a pointer to it
for(i=0;i<=n-1;i++)//initially non of the vertices are visited
visited[i]=false;//initially array with false,false,false
for(i=0;i<=n-1;i++)//this is necessary in view of directed and disconnected graph
{
if(!visited[i])//if ith vertex is not visited,call the function on vertex i,
//where i is the starting vertex of componant
traverse(i,visited);
}
}
void graph::traverse(int i,int *visited)
{
Node *p;//p is a ptr to node
if(!visited[i])//if ith vertex is not visited,visit it now
{
cout<<i;
visited[i]=true;//mark the ith vertex as visited vertex
//process ith adjacent vertices of ith vertex
for(p=a[i].fist;p!=NULL;p=p->link)
{
if(!visited[p->data])//if adjacent vertex is not visited,
//call the same function on adjacent vertex
traverse(p->data,visited);
}
}
}
void menu()
{
cout<<"1.Display the graph\n";
cout<<"2.No of vertices &edges of graph\n";
cout<<"3.Degree of each vertex in the graph\n";
cout<<"4.Bread First Search \n";
cout<<"5.Dfs\n";
cout<<"6.exit\n";
}
void main()
{
graph g;//vertices
int ch;
g.create();//create a graph whose address is stored in object g
clrscr();
menu();
count<<"enter your choice\n";
cin>>ch;
while(ch<6)
{
switch(ch)
{
case 1:{
g.display();
break;
}//case
case 2:{
//nov() returns no of vertices and edges
cout<<"No of vertices are="<<g.nov()<<"\n";
cout<<"No. edges="<<g.noe()<<"\n";
break;
}//case 2
case 3:
{
//i is the vertex no, degree of i is the degree of i is the
//degree of ith vertex, where i varies from 0 to no.of (vertices-1)
cout<<i<<"\t"<<g.degree(i)<<"\n";
break;
}
case 4:
{
g.bfs();//visit the graph in bfs
cout<<"\n";
break;
}
case 5:
{
g.dfs();//visit the graph in dfs
cout<<"\n";
break;
}
} //switch
menu();
cout<<"enter your choice\n";
cin>>ch;
}//while
getch();
}//main()
