使用矩阵实现伪代码：

Question

我需要以矩阵形式实现以下代码。我需要获取源顶点并随机生成连通图。但是，pseudo-code 是列表形式，我不确定我是否正确地将它转换为矩阵形式，出于某种原因，对于输出，我一直在让所有节点得到充分探索或它们的颜色变黑？

D代表距离

π代表parents

颜色 = 白色未访问/灰色 visited/black 所有邻居已探索

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

Answer 1

你的q.pop()放错地方了。由于它位于 for 循环的中间，因此您从队列中为每个从队列中处理的顶点删除 size 条目。您要做的是将 q.pop() 移动到 u=q.front().

之后

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

Answer 2

你只是偶尔把u和v搞错了，没有考虑伪代码的标识。

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

本来应该在 for 之后。还有，你做到了

g[v][0].color=black

而不是

g[u][0].color=black

和你在一起。再一次，同样的错误：

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

你什么时候应该写这个（和你）：

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

用 u 代替 v。否则没有任何意义。

我强烈建议阅读 BFS 背后的逻辑。 https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/

如果您确实了解 BFS 背后的逻辑并且恰好犯了这些错误，这里有 2 个调试技巧可以帮助我了解问题所在：

如果您的程序应该输出一些值，但没有输出，则可能存在循环。在中间阶段调试时使用 cout 通常是个好主意，看看结果是否符合您的预期。你可以在循环的情况下做类似的事情来注意循环在哪里，甚至可能为什么。

1.1。如果不知何故，无论你把 cout 放在哪里，你仍然没有得到输出，这可能是一个分段错误（在某些编码环境中它会说分段错误，有时你会看到它需要一段时间才能说出来类似于 "process has ended, returned some number that isn't 0" 可能类似于 "process has ended, returned -243" 在控制台中。分段错误是当您访问一些您不应该访问的内存时（您尝试访问的数组中的元素之一超出范围，或者您从列表中删除了该元素，而您正在尝试访问它。
一旦 q.pop() 被解决，你会注意到负的和大的输出（这在正常情况下是不可能的）。这意味着某处发生了溢出。您从除源之外的几乎所有节点的最大距离开始，溢出非常有意义，您以某种方式添加到具有最大值的节点。

编辑：关于随机生成，就像现在一样，实际上并不是那么随机。您应该使用带有种子（例如当前时间）的随机生成器，以便每次实际获得一棵新树。

在 c++ 中，有 srand，在这里您可以看到 https://www.cplusplus.com/reference/cstdlib/srand/ 中关于从 srand 获取实际随机数的快速示例（简单地初始化它而不带参数将使其每次都选择相同的种子，因此给出相同的结果但是，我们可以通过获取当前时间来修复它，因为当前时间总是不同的，并将其用作种子）：

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

使用矩阵实现伪代码：

Implementing the pseudocode using matrix:

c++

algorithm

breadth-first-search

clrs

graph-algorithm