Способы представления графа

Чтобы использовать какой-то алгоритм на графах, сам граф нужно каким-то образом представить в программе.

Рассмотрим два способа представления ориентированных и неориентированных графов (граф ориентированный, если у него заданы направления движения) 🌐

⓵ Матрица смежности

В данном способе заполняется матрицу размером V x V, где V- количество вершин графа:

A[i][j] = 1 — если существует ребро из i в j(в случае ориентированного графа записываем стоимость перехода из i в j
A[i][j] = 0 — ребра нет

(пример смотри на картинке)

⓶ Список смежности

В данном способе используется список D содержащий V списков. В каждом списке D[V] содержатся все вершины U, так что между V и U есть ребро.

(пример смотри на картинке)