I need to implement the following code however in a matrix form. I need to get the source vertex and randomly generate the connected graph. However, the pseudo-code is in the list form and I am not sure if I converted it to the matrix form correctly, for the output for some reason i keep getting all the nodes to be fully explored or the color of them all becomes black?
D represents distance
π represent parents
colour = white unvisited/ grey visited/black all neighbours explored
#include <iostream>
#include <limits>
#include <queue>
#include <stdlib.h> /* srand, rand */
using namespace std;
enum Color {white , gray, black};
struct vertex{
Color color =white ;
int relationship =0;
int distance =abs(numeric_limits<int>::max());
int parent =0;
};
void BFS(int size ,int s)
{
//no need for first loop to initializer to defaults since they are already
vertex g [size][size];
int random;
for(int i=0;i<size;i++)
{
for(int j=0;j<size;j++)
{
random =rand()%(size);
if(j!=i and random!=i) //to make it undirected
{
g[i][random].relationship=1;
g[random][i].relationship=1;
}
}
}
///
g[s][0].color =gray;
g[s][0].distance=0;
g[s][0].parent=0;
queue <int> q;
q.push(s);
int u;
while(!q.empty())
{
u=q.front();
q.pop();
g[u][0].color=black;
for(int v=0;v<size;v++)
{
if (g[u][v].relationship==1 and g[v][0].color==white) {
g[v][0].color = gray;
g[v][0].distance = g[u][0].distance+1;
g[v][0].parent = u;
q.push(v);
}
}
}
for(int i = 0; i<size;i++)
{
for(int j =0;j<size;j++)
{
cout<<g[i][j].relationship <<" ";
}
cout<<endl;
}
for(int i = 0; i<size;i++)
{
cout<<" Distance of node: " << i<<" from the source is: ";
cout<< g[i][0].distance<<" ";
if(g[i][0].color==white)
{
cout<<" Color of node: " << i<<" is white";
}
if(g[i][0].color==gray)
{
cout<<" Color of node: " << i<<" is gray";
}
if(g[i][0].color==black){
cout<<" Color of node: " << i<<" is black";
}
cout<<" parent of node: " << i<<" ";
cout<< g[i][0].parent<<" "<<" ";
cout<<endl;
}
}
int main() {
int vertices;
cout<<"Please enter the number of vertices: "<<endl;
cin>>vertices;
int source;
cout<<"Please enter the source "<<endl;
cin>>source;
BFS(vertices,source);
return 0;
}
Please login or Register to submit your answer