Проблема в том, что мне нужно создать случайный неориентированный график для проверки эталона Алгоритм Дейкстры используя массив и кучу для хранения вершин. AFAIK Реализация кучи должна быть быстрее массива при работе с разреженными и усредненными графами, однако, когда дело доходит до плотных графов, куча должна стать менее эффективной, чем массив.
Я попытался написать код, который будет генерировать граф на основе входных данных — количества вершин и общего числа ребер (максимальное число ребер в неориентированном графе равно 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;
}
Я получаю ошибку:
установить итератор без разыменования «при попытке создать граф из заданных данных.
Я знаю, что это как-то связано со стиранием элементов набора на лету, однако мне нужно стереть их как можно скорее, чтобы уменьшить использование памяти.
Может быть, есть лучший способ создать неориентированный граф? Мой довольно сырой, но это лучшее, что я придумал. Я думал о создании ориентированного графа, который является более простой задачей, но он не гарантирует, что каждые две вершины будут связаны.
Буду благодарен за любые советы и решения!
У Пиотри была та же идея, что и у меня, но он отступил на шаг.
Читайте только половину матрицы и игнорируйте диагональ для записи значений в. Если вы всегда хотите, чтобы у узла было ребро, добавьте его по диагонали. Если вы всегда не хотите, чтобы у узла было ребро, оставьте его как ноль.
Вы можете прочитать вторую половину своей матрицы для второго графика для тестирования вашей реализации.
Посмотрите на описание из std::set::erase
:
Срок действия итератора
В вашем коде, если next
равно it
стереть элемент std::set
от next
, вы не можете использовать it
, В этом случае вы должны (по крайней мере) изменить it
и только после этого продолжай использовать it
,