Implementing the pseudocode using matrix:

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

You just seem to have occasionally mistaken u with v and not taken into consideration the identation from the pseudo code.

            q.pop();
            g[v][0].color=black;

was meant to be after the for. Also, you did

g[v][0].color=black

instead of

g[u][0].color=black

with u. Again, the same mistake earlier:

                g[v][0].distance = g[v][0].distance+1;

when you should have written this(with u):

                g[v][0].distance = g[u][0].distance+1;

with u instead of v. It doesn't really make any sense otherwise.

I deeply suggest reading the logic behind BFS. https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/

In case you do actually know the logic behind BFS and just happened to do these mistakes, here are 2 debugging tips that helped me understand what was going wrong:

1. if your program should output some values, but doesn't, there is likely a loop. It is in general a good idea when debugging to use cout at intermediate stages, see if the result is what you expect. You can do similar things in the case of a loop to notice where the loop is and maybe even why.

   1.1. And if somehow, no matter where you put a cout, you still don't get output, it's possible there was a segmentation fault (in certain coding environments it will say segmentation fault, sometimes you will see that it will take a while before saying something like "process has ended, returned some number that isn't 0" possibly like "process has ended, returned -243" in the console. Segmentation fault is when you access some memory you shouldn't (one of the elements you are trying to access in an array is outside the bounds, or you deleted this element from a list and you are trying to access it).

2. Once q.pop() was solved, you noticed the negative and large output(which was impossible normally). This means that somewhere an overflow happened. You started with maximum distance for nearly all the nodes except the source, overflow made perfect sense, somehow you're adding to the nodes that have maximum.

Edit: About the random generation, as is right now, it's not actually that random. You should use a random generator with a seed, such as current time, to actually get a new tree each time.

In c++, there is srand, and here you can see a quick example from https://www.cplusplus.com/reference/cstdlib/srand/ about getting actual random numbers from srand ( simply initialising it without argument will make it pick the same seed each time and therefore give the same result However, we can fix it with getting the current time, as the current time will always be different, and using it as seed):

/* srand example */
#include <stdio.h>      /* printf, NULL */
#include <stdlib.h>     /* srand, rand */
#include <time.h>       /* time */

int main ()
{
  printf ("First number: %d\n", rand()%100);
  srand (time(NULL));
  printf ("Random number: %d\n", rand()%100);
  srand (1);
  printf ("Again the first number: %d\n", rand()%100);

  return 0;
}