Here is the implementation of Breadth First Search in C++ , which we discussed in the last post.
As,we said in last post, BFS is used to calculate the shortest distance, the distance matrix here actually takes care of that.
/*
BFS: The output may change depending on the order of input given
But the structure of graph remains same, i.e irrespective
of the order of given vertices, the distances computed remains same.
dis[MAX] --> is used to calculate distances of
nodes from the source vertex.
vertices count starting from 1 to N.
it uses adjacency list representation (with the help of vectors);
*/
#define NIL -1
#define white 0
#define gray 1
#define black 2
using namespace std;
int dis[MAX];
int parent[MAX];
int color[MAX];
vector<int> g[MAX];
void BFS(int s,int v)
{
int len,x,k;
queue<int> Q;
parent[s]=NIL;
dis[s]=0;
color[s]=gray;
Q.push(s);
while(!Q.empty())
{
x=Q.front();
Q.pop();
len=g[x].size();
for(int i=0;i<len;i++)
if(g[x][i] && color[g[x][i]]==white)
{
k=g[x][i];
color[k]=gray;
dis[k]=dis[x]+1;
parent[k]=x;
Q.push(k);
}
color[x]=black;
printf("%d ",x);
}
printf("\n***distances***\n");
for(int i=1;i<=v;i++)
printf("distance[%d]= %d\n",i,dis[i]);
return;
}
int main()
{
int v,e,s,d;
printf("Enter no of vertices: ");
scanf("%d",&v);
printf("Enter no of edges: ");
scanf("%d",&e);
for(int i=1;i<=e;i++)
{
printf("Enter source and destination: ");
scanf("%d %d",&s,&d);
g[s].push_back(d);
g[d].push_back(s);
}
printf("Enter source of graph: ");
scanf("%d",&s);
BFS(s,v);
return 0;
}
Check the BFS, on the graph discussed in the previous post, and verify the distance matrix to get an idea of structure of the graph.!
Superb :)
:)