2

问题是我需要创建一个随机无向图来测试Dijkstra 算法的基准，使用数组和堆来存储顶点。AFAIK 在稀疏图和平均图上运行时，堆实现应该比数组快，但是在密集图上，堆的效率应该比数组低。

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

在入口处，我将边的总数除以顶点的数量，这样每个顶点都有一个 const 的边数。该图由邻接表表示。这是我想出的：

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

我收到一个错误：

尝试从集合数据创建图形时，设置迭代器不可取消引用”。

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

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

我将不胜感激任何提示和解决方案！

4

2 回答 2

0

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

只读取一半矩阵，并忽略对角线写入值。如果您总是希望一个节点对自己有一条边，请在对角线上添加一条边。如果您总是不希望节点对自己有边，请将其保留为零。

您可以阅读矩阵的另一半以获取第二个图表，以测试您的实现。

于 2013-06-09T01:58:52.773 回答
0

看描述std::set::erase：_

迭代器有效性

  • 引用被函数删除的元素的迭代器、指针和引用无效。
  • 所有其他迭代器、指针和引用保持其有效性。

在您的代码中，如果next等于，并且您擦除by 的it元素，则不能使用. 在这种情况下，您必须（至少）更改并且仅在此之后继续使用 of 。std::setnextititit

于 2013-06-08T21:26:06.193 回答