Динамическое добавление в структуру данных графа

Question

Динамическое добавление в структуру данных графа

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

Мне нужно создать структуру данных DIRECTED graph, используя список смежности или матрицу в C ++, и добавить вершины / ребра из стандартного ввода, что означает динамически.

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

например, первая строка из стандартного ввода гласит:

Майами -> Нью-Йорк / 1100 -> Вашингтон / 1000 -> Альбукерке / 1700

Как я могу добавить ребро из Майами в Нью-Йорк, если нью-йоркская вершина еще не добавлена в график?

Спасибо всем за направление!

1

c++data-structures directed-graph dynamic vertex

Решение

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

Как насчет изменения размера списка смежности каждый раз, когда появляется новый уникальный узел? Вы можете поддерживать набор уникальных значений узлов и использовать его размер для настройки размера списка смежности каждый раз, когда вам нужно добавить узел. Ниже приведен код, который делает то же самое.

class Graph
{
public:
// Add links in the graph
void addLink(int id1, int id2){
// Add to hashset
uniqueNodes.insert(id1);
uniqueNodes.insert(id2);
// Resize on the adjacency list based on how many nodes exists in the uniqueNodes set
adjList.resize(uniqueNodes.size());
// Make the connections assuming undirected graph
adjList[id1].push_back(id2);
adjList[id2].push_back(id1);
}

// Print the graph
void printGraph(){
for(int i = 0; i < adjList.size(); i++){
cout << i << ":";
for(auto it = adjList[i].begin(); it != adjList[i].end(); it++)
cout << *it << "->";
cout << "NULL\n";
}
}

private:
// Adjacency list for the graph
vector<list<int>> adjList;
// Hashset to help define the size of the adjacency list as nodes come in
set<int> uniqueNodes;
};

0

Источник

Accepted Answer

как можно добавить ребро, которое
содержит вершину, которая еще не была создана

Просто: создайте его экземпляр ..

Я не вижу никаких проблем с этим. Предполагать V быть набором вершин, замеченным до сих пор. V изначально пуст. Как вы читаете вход x->yВы получаете свои конечные точки (x а также y). Если какой-либо из них не был создан (т.е. не V), вы создаете его и добавляете в набор вершин.

Другой способ взглянуть на это: представьте, что мы определяем график по его ребру E, По определению любое ребро является парой вершин, которая, в свою очередь, определяет множество вершин графа.

0