生成随机加权图的函数在某个阈值边缘后冻结

Question

所以我试图通过让节点 1、2、3、...、n 和边成为存储边 1 的端点、端点的三元组数组来生成具有 n 个节点和 n*4 条边的随机图边 2 和边的权重：

struct edge{
    int endpoint1;
    int endpoint2;
    int weight;
};

这是生成边数组（三元组）的函数：

edge* generateRandomGraph(int nrOfNodes)
{
    int adjMatrix[nrOfNodes+1][nrOfNodes+1] = {0};

    int nrOfEdges = nrOfNodes*4 ;

    edge *edges = new edge[nrOfNodes+1];
    
    int counter = 0;

    while(counter < nrOfEdges)
    {
        int a = 1 + rand() % nrOfNodes;
        int b = 1 + rand() % nrOfNodes;

        if(a != b)
        if(adjMatrix[a][b] == 0)
        {
            adjMatrix[a][b] = 1;
            adjMatrix[b][a] = 1;
            edges[counter].endpoint1 = a;
            edges[counter].endpoint2 = b;
            edges[counter].weight = rand() % 100;
            counter++;
        }
    }
                        
    return edges;
}

它在元素边缘 [31] 冻结时一直正常运行到一个点。可能是什么问题呢？调试器没有指定任何错误，但是当我尝试打印它中断的值时。也许是一些分段错误，因为数组的填充是基于 rand() 的？

Answer 1

这行不通有两个原因。

1. c++中没有变长数组。但是您可能会在编译器中使用自定义扩展来使其工作。无论如何，你不应该这样做，因为如果内存被分配，一个中等大小的图可能会破坏你的堆栈。
2. 你的

   edges

   数组被分配来容纳

   numberOfNodes+1

   元素，但它应该容纳

   numberOfEdges

   。你有一个内存溢出，从那时起你就在 UB-land.

对于这两个问题，请使用

std::vector

，您可以将其预先分配到您需要的大小。多亏了移动语义，你可以在不损失性能的情况下返回向量对象。

  std::vector<edge> edges;
  edges.reserve(numberOfEdges); // not +1

  // ... later ...

    edges.push_back(edge{a, b, weight});

  // ...

  return edges;

另外，我强烈建议不要使用

rand()

，而是

std::mt19937

。