Проблема в том, что мне нужно создать случайный неориентированный граф для тестирования эталонного теста алгоритма Дейкстры использование массива и кучи для хранения вершин. Насколько мне известно, реализация кучи должна быть быстрее, чем массив, при работе на разреженных и средних графах, однако, когда дело доходит до плотных графов, куча должна стать менее эффективной, чем массив.
Я попытался написать код, который будет создавать граф на основе входных данных - количества вершин и общего количества ребер (максимальное количество ребер в неориентированном графе равно 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;
}
Я получаю сообщение об ошибке:
установить итератор, не допускающий разыменования» при попытке создать график из заданных данных.
Я знаю, что это как-то связано со стиранием элементов набора на лету, однако мне нужно стереть их как можно скорее, чтобы уменьшить использование памяти.
Может быть, есть лучший способ создать неориентированный граф? Мой довольно сырой, но это лучшее, что я придумал. Я думал о создании ориентированного графа, который является более простой задачей, но он не гарантирует, что каждые две вершины будут связаны.
Буду признателен за любые советы и решения!