Попытка реализовать граф с использованием массива векторов

Question

Я пытаюсь реализовать граф, используя массив векторов. У меня невероятно трудное время. Векторы будут удерживать вершины, смежные с вершиной v, которая является индексом массива с именем uvertices.

Это то, что у меня есть до сих пор.

class Graph { 


public: 

    int V;   //this will represent the number of vertices in the graph 

std::vector<int>* vertices; 

Graph(int V) { 

    vertices = new std::vector<int>[V]; 

    } 

Здесь я создал (или думать и имел в виду, что они создали) массив размера V (V есть число вершин в графе), который содержит векторы. Я тогда хочу иметь возможность создавать края, поэтому у меня есть

void Graph::insert_edge(int v, int u) { 


} 

как способ. Я хочу, чтобы push_back значение u в вектор, содержащий список смежности вершины v. Каждый индекс моего массива векторов (с именем vertices) представляет собой идентификатор каждой вершины v на графике. Так что я хочу сделать что-то вроде

vertices[v].push_back(u); 

я с удивлением обнаружил, что, когда я напечатал вершины [v]., Intellisense дал мне список возможных функций, в том числе push_back. Причина, по которой я был удивлен, заключалась в том, что я фактически не создавал ни одного из векторов, но я оставил ее так. Это, очевидно, не работает, поэтому я начал отладку, и я понял, что всякий раз, когда я сначала вызываю insert_edge, он говорит мне, что размер и емкость моего массива «вершины» равны 0. Несмотря на то, что я создал свою структуру данных графа как

Graph G(8); 

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

Как сделать так, чтобы при вставке края я мог посмотреть на правильный индекс v в массиве вершин и получить доступ к функции push_back вектора, который имеет этот индекс массива, чтобы я мог добавить вершина u в список смежности вершины v.

Кроме того, я действительно искренне прошу, чтобы, если люди дадут мне опросы или проголосуют, чтобы закрыть мою тему, ПОЖАЛУЙСТА, дайте мне знать, почему. Это может быть так расстраивать, чтобы тратить время на то, чтобы написать все это и убедиться, что это ясно написано только для того, чтобы его проголосовали, даже если кто-нибудь даже не сказал мне, почему они меня голосуют.

Answer 1

Я с удивлением обнаружил, что когда я набрал вершин [v]., Intellisense предоставил мне список возможных функций, включая push_back. Причина, по которой я был удивлен, заключалась в том, что я фактически не создал ни одного из векторов.

Это не должно удивлять. Динамические массивы распределяются по времени выполнения, а intellisense и все остальные статические анализаторы не запускают код, поэтому они никогда не могут сказать, какое состояние переменной будет во время выполнения. Intellisense знает, что тип vertices[v] - это std::vector<int>, и он знает, какие функции-члены имеют этот тип.

Но вы не должны удивляться тому, что вы создали векторы. В конструкторе Graph.

я понял, что каждый раз, когда я первый звонок insert_edge, он говорит мне размер и емкость моего массива «вершин» является 0.

Существует недоразумение. vertices - указатель. И после запуска конструктора он указывает на блок памяти, который представляет собой динамический массив точно V экземпляров std::vector<int>. vertices не имеет таких членов, как size или capacity. После строительства каждый std::vector<int> внутри этого динамического массива равен пустой. Пока вы не нажмете вершин.

Это, очевидно, не работает.

Ваш insert_edge, похоже, работает нормально. Но у вас есть проблема с утечкой памяти (если у вас нет правильного деструктора, который вы не показывали), и проблема с неправильным конструктором копирования и оператором присваивания копии (не соблюдая правило три ... если вы не сделали этого это, но не показано). Вы можете исправить обе эти проблемы, используя вектор векторов вместо управления памятью вручную.

Как сделать это так, чтобы, когда ребро вставляется, я могу смотреть на правильный индекс V в массиве вершин, и получить доступ к функции push_back вектора, что этот индекс массива имеет место, так что я . можно добавить вершину и в списке смежности вершины у

Вы уже догадались:

vertices[v].push_back(u); 

Тот же синтаксис является правильным для вектора векторов тоже.

Вы также никогда не устанавливали Graph::V, но если вы используете вектор векторов, вам больше не нужно его в первую очередь, так как к нему можно получить доступ с помощью vertices.size().

Answer 2

Я думаю, вы должны тщательно рассмотреть свой выбор структур данных. В сообществе graph/algorithm два стандартных представления графов представляют собой списки смежности или матрицы смежности. См. Standard graph representations

Пожалуйста, мотивируйте, почему вы используете std :: vector и перефразируете вопрос. Связанные списки (как в представлении списка смежности) делают более эффективным удаление ребер, чем ваше векторное представление. То же самое касается матриц смежности.