#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
class NODE
{
public:
int edge[20][2],row,col,vn;
NODE *next;
void create();
void ad_mat();
void ad_list();
void dft(int);
void bft(int);
void eq(int);
int dq();
void push(int);
int pop();
};
NODE
*nw,*temp,*head[20];
int
visit[20],i,j,v,e;
int
a[20][20],top=-1,front=-1,rear=-1,v1,t,q[20],st[20],vertex;
void
NODE::create()
{
cout<<"\nEnter no. of
Vertices:";
cin>>v;
cout<<"\nEnter no. of
Edges:";
cin>>e;
for(i=1;i<=e;i++)
{
cout<<"\nEnter the
starting vertex of Edge "<<i<<":";
cin>>edge[i][1];
cout<<"\nEnter the ending
vertex of Edge "<<i<<":";
cin>>edge[i][2];
}
}
void
NODE::ad_mat()
{
cout<<"\nThe Adjacency matrix
is:\n";
for(i=1;i<=v;i++)
{
for(j=1;j<=v;j++)
{
a[i][j]=0;
}
}
for(i=1;i<=e;i++)
{
row=edge[i][1];
col=edge[i][2];
a[row][col]=1;
}
for(i=1;i<=v;i++)
cout<<"\t"<<i;
for(i=1;i<=v;i++)
{
cout<<"\n"<<i<<"\t";
for(j=1;j<=v;j++)
{
cout<<a[i][j]<<"\t";
}
}
}
void
NODE::ad_list()
{
for(i=1;i<=v;i++)
{
head[i]=new(NODE);
head[i]->vn=i;
head[i]->next=NULL;
}
for(i=1;i<=e;i++)
{
row=edge[i][1];
col=edge[i][2];
temp=head[row];
nw=new(NODE);
nw->vn=col;
nw->next=NULL;
while(temp->next!=NULL&&temp->next->vn<nw->vn)
{
temp=temp->next;
}
nw->next=temp->next;
temp->next=nw;
}
cout<<"\nThe adjacency list
is:\n";
for(i=1;i<=v;i++)
{
temp=head[i];
while(temp!=NULL)
{
cout<<temp->vn<<"->";
temp=temp->next;
}
cout<<"NULL \n";
}
}
void
NODE::dft(int v1)
{
for(i=1;i<=v;i++)
visit[i]=0;
push(v1);
visit[v1]=1;
while(top!=-1)
{
vertex=pop();
cout<<vertex;
temp=head[vertex]->next;
while(temp!=NULL)
{
if(visit[temp->vn]==0)
{
push(temp->vn);
visit[temp->vn]=1;
}
temp=temp->next;
}
}
}
void
NODE::bft(int)
{
for(i=1;i<=v;i++)
visit[i]=0;
eq(v1);
visit[v1]=1;
while(front!=rear)
{
vertex=dq();
cout<<vertex;
temp=head[vertex]->next;
while(temp!=NULL)
{
if(visit[temp->vn]==0)
{
eq(temp->vn);
visit[temp->vn]=1;
}
temp=temp->next;
}
}
}
void NODE::eq(int
t)
{
front++;
q[front]=t;
}
int NODE::dq()
{
rear++;
t=q[rear];
return(t);
}
void
NODE::push(int t)
{
top++;
st[top]=t;
}
int NODE::pop()
{
t=st[top];
top--;
return(t);
}
void main()
{
int sw;
NODE a;
clrscr();
do
{
cout<<"\n\n\n\n\n\tMenu\n1.Create
graph\n2.Adjacency matrix\n3.Adjacency list\n4.Depth first traversal\n5.Breadth
first treversal\n6.Exit\nEnter Choice:";
cin>>sw;
switch(sw)
{
case 1:
a.create();
break;
case 2:
a.ad_mat();
break;
case 3:
a.ad_list();
break;
case 4:
cout<<"\n
Enter starting vertex:";
cin>>v1;
a.dft(v1);
break;
case 5:
cout<<"\n
Enter starting vertex:";
cin>>v1;
a.bft(v1);
break;
case 6:
exit(0);
break;
default:
cout<<"\nEnter
correct choice";
break;
}
}while(sw<6);
}
-----------------------------OUTPUT------------------------------
Menu
1.Create graph
2.Adjacency
matrix
3.Adjacency list
4.Depth first
traversal
5.Breadth first
treversal
6.Exit
Enter Choice:1
Enter no. of
Vertices:7
Enter no. of
Edges:9
Enter the starting
vertex of Edge 1:1
Enter the ending
vertex of Edge 1:6
Enter the
starting vertex of Edge 2:6
Enter the ending
vertex of Edge 2:5
Enter the
starting vertex of Edge 3:5
Enter the ending
vertex of Edge 3:4
Enter the
starting vertex of Edge 4:4
Enter the ending
vertex of Edge 4:3
Enter the
starting vertex of Edge 5:3
Enter the ending
vertex of Edge 5:2
Enter the
starting vertex of Edge 6:2
Enter the ending
vertex of Edge 6:1
Enter the
starting vertex of Edge 7:2
Enter the ending
vertex of Edge 7:7
Enter the
starting vertex of Edge 8:7
Enter the ending
vertex of Edge 8:4
Enter the
starting vertex of Edge 9:7
Enter the ending
vertex of Edge 9:5
Menu
1.Create graph
2.Adjacency
matrix
3.Adjacency list
4.Depth first
traversal
5.Breadth first
treversal
6.Exit
Enter Choice:2
The Adjacency
matrix is:
1
2 3 4
5 6 7
1 0
0 0 0
0 1 0
2 1
0 0 0
0 0 1
3 0
1 0 0
0 0 0
4 0
0 1 0
0 0 0
5 0
0 0 1
0 0 0
6 0
0 0 0
1 0 0
7 0
0 0 1
1 0 0
Menu
1.Create graph
2.Adjacency
matrix
3.Adjacency list
4.Depth first
traversal
5.Breadth first
treversal
6.Exit
Enter Choice:3
The adjacency
list is:
1->6->NULL
2->1->7->NULL
3->2->NULL
4->3->NULL
5->4->NULL
6->5->NULL
7->4->5->NULL
Menu
1.Create graph
2.Adjacency
matrix
3.Adjacency list
4.Depth first
traversal
5.Breadth first
treversal
6.Exit
Enter Choice:4
Enter starting
vertex:1
1654327
Menu
1.Create graph
2.Adjacency
matrix
3.Adjacency list
4.Depth first
traversal
5.Breadth first
treversal
6.Exit
Enter Choice:5
Enter starting vertex:1
1654327
Menu
1.Create graph
2.Adjacency
matrix
3.Adjacency list
4.Depth first
traversal
5.Breadth first
treversal
6.Exit
Enter Choice:6
This is dummy text. It is not meant to be read. Accordingly, it is difficult to figure out when to end it. But then, this is dummy text. It is not meant to be read. Period.