Что такое граф?
Урок 2 из 14 курса Графы — Серия «Структуры данных» №9 на Coddy.
Граф — это структура данных, которая моделирует набор объектов и связей между ними. Объекты называются вершинами (или узлами), а связи — ребрами.
Графы повсюду. Социальные сети — это графы (люди — вершины, дружба — ребра). Дорожные карты — это графы (перекрестки — вершины, улицы — ребра). Интернет, деревья зависимостей и игровые карты — все это графы.
В этом курсе мы сосредоточимся на неориентированном графе: если ребро соединяет u и v, то v также соединено с u. Направления нет. Для простоты мы будем использовать целые числа в качестве ключей вершин.
Внутри мы будем хранить граф в виде списка смежности: словаря (map), где каждому значению вершины соответствует список её соседей. Это позволяет получать доступ к соседям вершины за одно обращение к словарю, что и требуется большинству алгоритмов на графах.
Операции, которые мы реализуем в нашем классе Graph:
- addVertex: Добавить новую вершину, пока без ребер.
- addEdge: Соединить две вершины.
- hasEdge: Проверить, соединены ли две вершины.
- getNeighbors: Получить список соседей вершины.
- removeEdge: Разорвать связь между двумя вершинами.
- size: Посчитать, сколько вершин в графе.
Давайте создадим класс Graph!
Попробуйте сами
В этом уроке нет задания по программированию.