~ 565 - 567 дни 👨‍💻 | Графы

Последние дни знакомился с графами.

Графы - это структура связанных данных. Она состоит из вершин и ребёр.
Рёбра - это связи между вершинами.

Графы похожи на деревья. Точнее деревья являются частным случаем графов.

Смежные вершины - это вершины непосредственно связанные между собой.
Вершины могут быть связаны между собой цепочкой промежуточных вершин.

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

Направленный граф (ориентированный) - это граф с рёбрами, у которых есть направление.

Циклический граф - это направленный граф, ребра которых замыкаются в кольцо. В таком случае возможен бесконечный цикл.
Ациклический граф не имеет подобного кольца.

Взвешенный граф - это граф, ребра которого имеют свой вес. Например, указано расстояние между городами.

Вершины обычно хранятся в виде объектов класса в массиве.
Рёбра (т.е. связи между вершинами) реализуются 2-мя способами:
1) Матрица смежности;
2) Список смежности;

Реализовал структуру данных и методы вставки вершины/связи, удаления вершины/связи, проверка смежности вершин.

Покрыл код тестами.

P.s. как здорово, что прошлым летом я прорешал большое кол-во маленьких задач по работе с матрицами на python. 🤓

С кодом можно ознакомиться на гитхаб:
https://github.com/avagners/algorithms_and_data_structures/tree/main/data_structures/graph