Чтобы использовать какой-то алгоритм на графах, сам граф нужно каким-то образом представить в программе.
Рассмотрим два способа представления ориентированных и неориентированных графов (граф ориентированный, если у него заданы направления движения) 🌐
⓵ Матрица смежности
В данном способе заполняется матрицу размером V x V, где V- количество вершин графа:
A[i][j] = 1 — если существует ребро из i в j(в случае ориентированного графа записываем стоимость перехода из i в j
A[i][j] = 0 — ребра нет
(пример смотри на картинке)
⓶ Список смежности
В данном способе используется список D содержащий V списков. В каждом списке D[V] содержатся все вершины U, так что между V и U есть ребро.
(пример смотри на картинке)
Авторизуйтесь, чтобы оставить комментарий.