DSPS: Revised version of GRAPHS (BFS)
#include<iostream>
using namespace std;
#define size 10
#define true 1
#define false 0
class graph
{
public:
int g[size][size];
int visit[size],rear,front,q[size];
int n,e;
public:
graph();
void getmatrix();
void displaygraph();
void bfs(int);
};
graph::graph()
{
for(int i=0;i<size;i++)
{
for(int j=0;j<size;j++)
{
g[i][j]=false;
}
}
for(int i=0;i<size;i++)
{
visit[i]=false;
}
}
void graph::getmatrix()
{
int v1,v2;
cout<<"Enter no. of nodes:";
cin>>n;
cout<<"Enter no. of edges:";
cin>>e;
for(int i=0;i<e;i++)
{
cout<<"Enter edge in the form of V1 and V2:";
cin>>v1>>v2;
g[v1][v2]=g[v2][v1]=true;
}
cout<<"Entered Graph is"<<endl;
for(int k=0;k<n;k++)
{
cout<<"|";
for(int l=0;l<n;l++)
{
cout<<g[k][l]<<"\t";
}
cout<<"|";
cout<<endl;
}
}
void graph::bfs(int v1)
{
int v2;
front=rear=-1;
visit[v1]=true;
q[++rear]=v1;
while(front!=rear)
{
v1=q[++front];
cout<<v1<<" ";
for(v2=0;v2<n;v2++)
{
if(g[v1][v2]==true && visit[v2]==false)
{
q[++rear]=v2;
visit[v2]=true;
}
}
}
}
int main()
{
graph g;
int v;
g.getmatrix();
cout<<"enter the starting vertex for BFS traversal";
cin>>v;
cout<<"The BFS tarversal is:";
g.bfs(v);
return 0;
}
using namespace std;
#define size 10
#define true 1
#define false 0
class graph
{
public:
int g[size][size];
int visit[size],rear,front,q[size];
int n,e;
public:
graph();
void getmatrix();
void displaygraph();
void bfs(int);
};
graph::graph()
{
for(int i=0;i<size;i++)
{
for(int j=0;j<size;j++)
{
g[i][j]=false;
}
}
for(int i=0;i<size;i++)
{
visit[i]=false;
}
}
void graph::getmatrix()
{
int v1,v2;
cout<<"Enter no. of nodes:";
cin>>n;
cout<<"Enter no. of edges:";
cin>>e;
for(int i=0;i<e;i++)
{
cout<<"Enter edge in the form of V1 and V2:";
cin>>v1>>v2;
g[v1][v2]=g[v2][v1]=true;
}
cout<<"Entered Graph is"<<endl;
for(int k=0;k<n;k++)
{
cout<<"|";
for(int l=0;l<n;l++)
{
cout<<g[k][l]<<"\t";
}
cout<<"|";
cout<<endl;
}
}
void graph::bfs(int v1)
{
int v2;
front=rear=-1;
visit[v1]=true;
q[++rear]=v1;
while(front!=rear)
{
v1=q[++front];
cout<<v1<<" ";
for(v2=0;v2<n;v2++)
{
if(g[v1][v2]==true && visit[v2]==false)
{
q[++rear]=v2;
visit[v2]=true;
}
}
}
}
int main()
{
graph g;
int v;
g.getmatrix();
cout<<"enter the starting vertex for BFS traversal";
cin>>v;
cout<<"The BFS tarversal is:";
g.bfs(v);
return 0;
}
Comments
Post a Comment