使用矩阵实现伪代码：

Question

但是我需要以矩阵形式实现以下代码。我需要获取源顶点并随机生成连接的图。但是，伪代码是列表形式的，由于没有输出，所以我不确定是否将其正确转换为矩阵形式。

D代表距离

π代表父母

颜色=未访问白色/已访问灰色/已探查所有邻居都是黑色

#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][j].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();
        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[v][0].distance+1;
                g[v][0].parent = u;
                q.push(v);
            }
            q.pop();
            g[v][0].color=black;
        }
    }
for(int i = 0; i<size;i++)
{//output the color distance and the parent
    cout<<"Node: " <<i<<endl;
    cout<< g[i][0].color<<" ";
    cout<< g[i][0].distance<<" ";
    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;
}

Answer 1

您的q.pop()放在错误的位置。由于它位于for循环的中间，因此对于从队列中处理的每个顶点，都从队列中删除size条目。您要做的是将q.pop()移到u=q.front()之后。

u = q.front();
q.pop();
for(int v = 0; v < size; v++)