Исходя из определения графа (туть) можно хранить граф в виде списка вершин и списка ребер.
Подобная структура позволяет легко проверить наличие вершины и ребра (A in V ), но задача проверки всех соседей становиться довольно сложной, т.к. нам надо перебрать весь список E и сопоставить его с V.
Среди различных способов представления графов выделяют два самых популярных:
- списки смежности
- матрицы смежности.
Оба способа подходят для представления как ориентированных, так и неориентированных графов.
Матрица смежности
Она подходит для простых графов.
Матрица смежности всегда имеет размер |V| x |V| (квадратная):
В Python такую структуру легко реализовать как список списков, т.е.:
G = [ [0, 1, 1, 1, 0, 0], [1,0, 0, 0, 1, 0] , [1, 0, 0, 1, 1, 0] , [1, 0, 1, 0, 0, 1] , ... ]
Особенности такой структуры:
· Все петли находятся на главной диагонали.
· Если граф не ориентирован, то граф будет симметричен относительно главной диагонали.
· Степень вершины – сумма единиц в строке
Проверка наличия ребра (соседства двух вершин): - O(1) – по сути мгновенно, т.к. мы сразу по индексу элемента матрицы проверяем значение ячейки. Например, A[1][1] = 0 – ребра нет, A[1][0] = 1 – ребро есть
Перебор всех соседей: O(V) – проходимся по строке и смотрим значение ячеек
Плюс: простота реализации
Минус: объемная структура и как следствие занимает много памяти, может оказаться неэффективным способом хранения дерева или разреженных графов. Требует O(|V|² ) памяти
Программная реализация заполнения матрицы:
Списки смежности
Второй способ заключается в том, чтобы просто хранить для каждой вершины список её соседей.
Проверка ребра (соседства вершин) – O(1)
Перебор соседей – О(neighbor), где neighbor – реальное количество соседей, быстрее их перебрать просто нельзя.
Программная реализация заполнения списка смежности:
Данный способ представления больше подходит для разреженных графов, то есть графов у которых количество рёбер гораздо меньше чем количество вершин в квадрате ( |E| << |V|2 ).
Плюс: Память требуемая для представления равна O(|E| + |V|) что является лучшим показателем чем матрица смежности для разреженных графов.
Минус: нет быстрого способа проверить существует ли ребро. Требуется О(neighbor) (u, v), что медленнее чем О(1) в матрице смежности.
В качестве вывода:
Когда же использовать какую структуру?
Матрица смежности больше подходит для неразреженных(плотных) графов
Список смежности - для разреженных графов
Плотный граф - это граф, имеющий число ребер близкое к максимально возможному.
Разреженный граф - это граф, имеющий малое число рёбер(т.е. много меньше числа вершин).