c++ - 在 C++ 中创建随机无向图

Question

问题是我需要创建一个随机无向图来测试 Dijkstra's algorithm 的基准使用数组和堆来存储顶点。据我所知，当在稀疏图和平均图上运行时，堆实现应该比数组更快，但是当涉及到密集图时，堆的效率应该低于数组。

我尝试编写代码，根据输入生成图 - 顶点数和边总数(无向图中的最大边数为 n(n-1)/2)。

在入口处，我将边的总数除以顶点的数量，这样我就有了来自每个顶点的常量边。该图由邻接表表示。这是我想出的:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <list>
#include <set>

#define MAX 1000
#define MIN 1

class Vertex
{
public:
    int Number;
    int Distance;
    Vertex(void);
    Vertex(int, int);
    ~Vertex(void);
};

Vertex::Vertex(void)
{
    Number = 0;
    Distance = 0;
}

Vertex::Vertex(int C, int D)
{
    Number = C;
    Distance = D;
}

Vertex::~Vertex(void)
{
}


int main()
{
    int VertexNumber, EdgeNumber;

    while(scanf("%d %d", &VertexNumber, &EdgeNumber) > 0)
    {
        int EdgesFromVertex = (EdgeNumber/VertexNumber);

        std::list<Vertex>* Graph = new std::list<Vertex> [VertexNumber];

        srand(time(NULL));

        int Distance, Neighbour;
        bool Exist, First;

        std::set<std::pair<int, int>> Added;

        for(int i = 0; i < VertexNumber; i++)
        {
            for(int j = 0; j < EdgesFromVertex; j++)
            {
                First = true;
                Exist = true;

                while(First || Exist)
                {
                    Neighbour = rand() % (VertexNumber - 1) + 0;

                    if(!Added.count(std::pair<int, int>(i, Neighbour)))
                    {
                        Added.insert(std::pair<int, int>(i, Neighbour));
                        Exist = false;
                    }
                    First = false;
                }
            }

            First = true;
            std::set<std::pair<int, int>>::iterator next = Added.begin();

            for(std::set<std::pair<int, int>>::iterator it = Added.begin(); it != Added.end();)
            {
                if(!First)
                    Added.erase(next);

                Distance = rand() % MAX + MIN;

                Graph[it->first].push_back(Vertex(it->second, Distance));
                Graph[it->second].push_back(Vertex(it->first, Distance));

                std::set<std::pair<int, int>>::iterator next = it;
                First = false;
            }
        }

        // Dijkstra's implementation
    }

    return 0;
}

我得到一个错误:

set iterator not dereferencable" when trying to create graph from set data.

我知道它与动态删除集合元素有关，但我需要尽快删除它们以减少内存使用。

也许有更好的方法来创建一些无向图？我的很原始，但这是我想出的最好的。我正在考虑制作一个更容易完成的有向图，但它不能确保每两个顶点都会连接。

如果有任何提示和解决方案，我将不胜感激!

Answer 1

Piotry 的想法与我基本相同，但他少了一步。

只读取矩阵的一半，而忽略你对角线的写入值。如果您总是希望节点自身有边，请在对角线处添加一个边。如果您始终不希望节点与自身有边，请将其保留为零。

您可以阅读矩阵的另一半以获得第二张图来测试您的实现。