/******************************************************
NAME : Jabir Daud Pathan
PROGRAM : Represent graph using adjacency list
and perform DFS and BFS
*******************************************************/
/*---------------<<
Header File >>------------------*/
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
#define
size 10
/*----------<< Declaration of class graph
>>---------*/
class
graph
{
private:
struct node
{
int vertex;
node*next;
};
node*head[size];
public :
void create();
void insert(int,int);
void bfs(int);
void dfs(int);
};
int
visit[size];
/*----------<< Declaration of class Queue
>>---------*/
class
Q
{
public:
int front ,rear;
int q[size];
public:
Q()
//Default Constructor
{
front=rear=-1;
}
void
enter(int x)
{
if(empt())
rear=front=0;
else
rear++;
q[rear]=x;
}
int delet()
{
int x;
x=q[front];
if(rear==front)
rear=front=-1;
else
front++;
return x;
}
int empt()
{
if(rear==-1)
return 1;
else
return 0;
}
};
/*----------<<
Function Defination for Create Graph >>------------*/
void
graph:: create()
{
int i,vi,vj,no,n;
cout<<"\n\nEnter the no of
vertices==>";
cin>>n;
for(i=0;i<n;i++)
head[i]=NULL;
cout<<"\n\nEnter the no. of
edges==>";
cin>>no;
for(int j=0;j<no;j++)
{
cout<<"\n\nEnter an edge
==>";
cin>>vi>>vj;
insert(vi,vj);
insert(vj,vi);
}
}
/*----<<
Function Defination for Insertion Element >>-------*/
void
graph::insert(int v1,int v2)
{
node *p,*q;
q=new node;
q->vertex=v2;
q->next=NULL;
if(head[v1]==NULL)
head[v1]=q;
else
{
p=head[v1];
while(p->next!=NULL)
p=p->next;
p->next=q;
}
}
/*----<<
Function Defination for BFS Traversal >>-------*/
void
graph::bfs(int x)
{
int y,j;
Q q1;
node *p;
q1.enter(x);
cout<<" "<<x;
visit[x]=1;
while(!q1.empt())
{
y=q1.delet();
for(p=head[y];p!=NULL;p=p->next)
{
j=p->vertex;
if(visit[j]==0)
{
q1.enter(j);
visit[j]=1;
cout<<" "<<j;
}
}
}
}
/*----<<
Function Defination for DFS Traversal >>-------*/
void
graph :: dfs(int v1)
{
node*p;
cout<<" "<<v1;
p=head[v1];
visit[v1]=1;
while(p!=NULL)
{
v1=p->vertex;
if(!visit[v1])
dfs(v1);
p=p->next;
}
}
/*-------------<< Main Function Starts >>------------*/
void
main()
{
int v1,ch;
char ans;
graph g;
clrscr();
do
{
cout<<"\n\n\t\t\t-------<<
MENU >>-------";
cout<<"\n\t\t\t1.Create
Graph";
cout<<"\n\t\t\t2.BFS";
cout<<"\n\t\t\t3.DFS";
cout<<"\n\t\t\t4.Exit";
cout<<"\n\t\t\t---------------------------";
cout <<"\n\t\t\tEnter Your
Choice : ";
cin>>ch;
switch(ch)
{
case 1 :
g.create();
break;
case 2 :
for(int j=0;j<size;j++)
visit[j]=0;
cout<<"\n\nEnter the vertex
from which you want to traverse graph :";
cin>>v1;
cout<<"\n\nBFS TRAVERSAL :
";
g.bfs(v1);
break;
case 3 :
for( j=0;j<size;j++)
visit[j]=0;
cout<<"\n\nEnter the vertex
from which you want to traverse graph :";
cin>>v1;
cout<<"\n\nDFS TRAVERSAL :
";
g.dfs(v1);
break;
case 4 :
exit(0);
break;
}
cout<<"\n\n\n\tDo you want to
continue(y/n): ";
ans=getche();
}while(ans=='y'||ans=='Y');
getch();
}
/*-------------<< End Of Main Function >>---------------*/
/*-----------------<< OUTPUT
SCREEN >>-------------------*/
-------<< MENU
>>-------
1.Create Graph
2.BFS
3.DFS
4.Exit
---------------------------
Enter Your Choice : 1
Enter
the no of vertices==>6
Enter
the no. of edges==>10
Enter
an edge ==>0 1
Enter
an edge ==>0 4
Enter
an edge ==>0 5
Enter
an edge ==>1 5
Enter
an edge ==>1 3
Enter
an edge ==>1 2
Enter
an edge ==>3 2
Enter
an edge ==>3 5
Enter
an edge ==>3 4
Enter
an edge ==>4 5
Do you want to continue(y/n):y
-------<< MENU
>>-------
1.Create Graph
2.BFS
3.DFS
4.Exit
---------------------------
Enter Your Choice : 2
Enter
the vertex from which you want to traverse graph :0
BFS
TRAVERSAL : 0 1 4 5 3 2
Do you want to continue(y/n): y
-------<< MENU
>>-------
1.Create Graph
2.BFS
3.DFS
4.Exit
---------------------------
Enter Your Choice : 3
Enter
the vertex from which you want to traverse graph :0
DFS
TRAVERSAL : 0 1 5 3 2 4
Do you want to continue(y/n):y
-------<< MENU
>>-------
1.Create Graph
2.BFS
3.DFS
4.Exit
---------------------------
Enter Your Choice : 4
No comments:
Post a Comment