Представление графа через Set и hash суммы

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

Набор отличается от вектора 2мя вещами:

1. он хранит элементы в отсортированном порядке (так как мы используем Set)

2. дублирование элементов не допускается (так как по прежнему, это свойство самого Set)

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

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

На картинке представлен пример того самого сета.

Завтра рассмотрим оптимизацию данного подхода

Data Science: Алгоритмы и Структуры данных