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

Question

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

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

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

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

Майами -> Нью-Йорк/1100 -> Вашингтон/1000 -> Albuquerque/1700

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

Спасибо за руководство всем!

Answer 1

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

просто: его экземпляр ..

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

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