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

Направленный против ненаправленного

Существует два типа кромок:

  • Ненаправленные ребра имеют двустороннее соединение. А к Б или Б к А.
  • Направленные ребра имеют одностороннее соединение. Только от С до D.

Все ребра неориентированного графа имеют неориентированные ребра, а все ребра ориентированного графа имеют направленные ребра. Неориентированное ребро можно представить с помощью неупорядоченной пары {A,B}. Направленное ребро может быть представлено с помощью упорядоченной пары (C,D), где первый элемент является источником, а второй элементом является пунктом назначения.

Использование графиков

Графики используются повсеместно. Одним из примеров являются социальные сети. Существует направленное или ненаправленное соединение между пользователем и другим пользователем. Facebook использует неориентированные графы для отображения дружеских отношений между пользователями. Если кто-то является вашим другом, вы также являетесь его другом. Twitter использует ориентированные графы для отображения отношений. Вы можете следить за знаменитостями, но шансы, что они подпишутся на вас, ничтожны. Механизмы рекомендаций для потоковых сервисов имеют несколько телешоу или фильмов, похожих на ваши последние просмотренные шоу или фильмы. Существует непрямая связь между фильмами из-за их жанра, сюжета, актеров или режиссеров.

Взвешенные графики

На графиках иногда бывают места, где одни связи могут быть предпочтительнее других. Например, поиск наиболее оптимального пути на картах Google. Отправляясь куда-то, вы хотите найти кратчайший путь туда.

Если я хочу добраться из города А в город F, я могу добраться туда разными способами. Каждая «дорога» имеет для них определенный вес. Допустим, чем меньше вес, тем меньше времени вы тратите на эту «дорогу». Другие факторы, такие как интенсивность движения и ограничение скорости, влияют на вес «дороги». Самый быстрый маршрут из города A в город F — это A -> B -> F.

Циклический против ациклического

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

Ациклический граф — это ориентированный граф без ориентированных циклов. Каждое ребро вершин указывает на другое, так что они никогда не образуют замкнутый цикл. Невозможно перейти из вершины E в вершину A.

Спасибо за чтение. В следующей статье мы рассмотрим хранение и реализацию графов.

Ресурсы

Для получения дополнительных ресурсов по графикам я предлагаю просмотреть эти полезные ссылки.

https://medium.com/swlh/data-structures-graphs-50a8a032db03

https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/

https://medium.com/basecs/a-gentle-introduction-to-graph-theory-77969829ead8