Создание случайного неориентированного графа в переполнении стека

Проблема в том, что мне нужно создать случайный неориентированный график для проверки эталона Алгоритм Дейкстры используя массив и кучу для хранения вершин. 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;
}

Я получаю ошибку:

установить итератор без разыменования «при попытке создать граф из заданных данных.

Я знаю, что это как-то связано со стиранием элементов набора на лету, однако мне нужно стереть их как можно скорее, чтобы уменьшить использование памяти.

Может быть, есть лучший способ создать неориентированный граф? Мой довольно сырой, но это лучшее, что я придумал. Я думал о создании ориентированного графа, который является более простой задачей, но он не гарантирует, что каждые две вершины будут связаны.

Буду благодарен за любые советы и решения!

2

Решение

У Пиотри была та же идея, что и у меня, но он отступил на шаг.

Читайте только половину матрицы и игнорируйте диагональ для записи значений в. Если вы всегда хотите, чтобы у узла было ребро, добавьте его по диагонали. Если вы всегда не хотите, чтобы у узла было ребро, оставьте его как ноль.

Вы можете прочитать вторую половину своей матрицы для второго графика для тестирования вашей реализации.

0

Другие решения

Посмотрите на описание из std::set::erase :

Срок действия итератора

  • Итераторы, указатели и ссылки, ссылающиеся на элементы, удаленные
    функция недействительна.
  • Все остальные итераторы, указатели и
    ссылки сохраняют свою актуальность.

В вашем коде, если next равно itстереть элемент std::set от next, вы не можете использовать it, В этом случае вы должны (по крайней мере) изменить it и только после этого продолжай использовать it,

0

По вопросам рекламы [email protected]