时间戳

首页 > 解决方案 > 使用矩阵实现伪代码：

c++ - 使用矩阵实现伪代码：

问题描述

我需要以矩阵形式实现以下代码。我需要获取源顶点并随机生成连通图。但是，伪代码是列表形式，我不确定我是否将它正确转换为矩阵形式，由于某种原因，我不断让所有节点得到充分探索，或者它们的颜色都变成黑色?

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

标签： c++algorithmgraph-algorithmbreadth-first-searchclrs

解决方案

您似乎只是偶尔将 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 个调试技巧可以帮助我了解问题所在：

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

    1.1。如果不知何故，无论你把cout放在哪里，你仍然没有得到输出，这可能是一个分段错误（在某些编码环境中它会说分段错误，有时你会看到它需要一段时间才能说诸如“进程已结束，返回一些非 0 的数字”之类的内容可能类似于控制台中的“进程已结束，返回 -243”。分段错误是当您访问一些您不应该访问的内存时（您的元素之一尝试访问数组超出范围，或者您从列表中删除了此元素并且您正在尝试访问它）。

  2. 一旦 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;
}

推荐阅读