Garmaine Staff asked 2 years ago

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

enter image description here

     #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;
}