Составление списка смежности в C ++ для ориентированного графа

Вы можете использовать вектор в узле, как список смежности.

class node {
int value;
vector<node*> neighbors;
};

Если график известен во время компиляции, вы можете использовать массив, но это «немного» сложнее. Если вы знаете только размер графика (во время компиляции), вы можете сделать что-то подобное.

template<unsigned int N>
class graph {
array<node, N> nodes;
}

Чтобы добавить соседа, вы делаете что-то подобное (не забывайте нумерацию с нуля):

nodes[i].neighbors.push_back(nodes+j); //or &nodes[j]

Конечно, вы можете сделать список смежности без указателей и работать «над» таблицей. Чем у тебя есть vector<int> в узле и вы нажимаете номер соседа. Используя оба представления графа, вы можете реализовать все алгоритмы, которые используют список смежности.

И, наконец, я мог бы добавить. Некоторые используют список вместо вектора, потому что удаление в O (1) время. Ошибка. Для большинства алгоритмов порядок в списке смежности не важен. Таким образом, вы можете стереть любой элемент из вектора в O (1) время. Просто поменяйте местами с последним элементом, pop_back является O (1) сложность. Что-то вроде того:

if(i != number_of_last_element_in_list) //neighbors.size() - 1
swap(neighbors[i], neighbor.back());
neighbors.pop_back();

Конкретный пример (у вас есть вектор в узле, C ++ 11 (!)):

//creation of nodes, as previously
constexpr unsigned int N = 3;
array<node,N> nodes; //or array<node, 3> nodes;
//creating edge (adding neighbors), in the constructor, or somewhere
nodes[0].neighbors = {&nodes[1]};
nodes[1].neighbors = {&nodes[0], &nodes[1]};
//adding runtime, i,j from user, eg. i = 2, j = 0
nodes[i].neighbors.push_back(&nodes[j]); //nodes[2].neighbors = {&nodes[0]};

Я верю, что это понятно. От 0 ты можешь пойти в 1, от 1 в 0 и к себе, и (как, например,) из 2 в 0, Это ориентированный граф. Если вы хотите ненаправленный, вы должны добавить к соседним узлам адреса соседей. Вы можете использовать цифры вместо указателей. vector<unsigned int> в class node и отталкивая номера, без адресов.

Как мы знаем, вам не нужно использовать указатели. Вот пример этого тоже.

Когда количество вершин может измениться, вы можете использовать вектор узлов (vector<node>) вместо массива, и просто изменение размера. Остальное остается без изменений. Например:

vector<node> nodes(n); //you have n nodes
nodes.emplace_back(); //you added new node, or .resize(n+1)
//here is place to runtime graph generate
//as previously, i,j from user, but now you have 'vector<unsigned int>' in node
nodes[i].neighbors.push_back(j);

Но ты не может стереть узел, это нарушает нумерацию! Если вы хотите что-то стереть, вы должны использовать список (list<node*>) указателей. В противном случае вы должны оставить несуществующие вершины. Здесь порядок имеет значение!

По поводу линии nodes.emplace_back(); //adding node, Это безопасно с графом без указателей. Если вы хотите использовать указатели, вы преимущественно не должен изменить размер графика.
Вы можете случайно изменить адрес некоторых узлов при добавлении вершины, когда vector будет скопирован в новое место (из космоса).

Одним из способов справиться с этим является использование резерв, хотя вы должны знать максимальный размер графика! Но на самом деле я призываю вас не использовать vector сохранить вершины, когда вы используете указатели. Если вы не знаете реализацию, более безопасным может быть самостоятельное управление памятью (например, умные указатели. shared_ptr или просто новый).

node* const graph = new node[size]; //<-- It is your graph.
//Here no address change accidentally.

С помощью vector как список смежности всегда отлично! Нет возможности изменить адрес узла.