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

Допустим, у нас есть неориентированный граф G из V = 5 вершин и E = 6 рёбер. Вершины пронумерованы от 1 до 5, рёбра для удобства также пронумеруем буквами a, b, c, d, e. Одна вершина с петлёй, изолирована от других. 

Перечисление множеств

По определению, граф - это топологическая модель, которая состоит из множества вершин и множества рёбер, их соединяющих. Значит, самый “простой” способ представить граф - определить оба этих множества.

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

Недостаток такого подхода: использование достаточно тяжеловесной структуры – хэш таблицы – для хранения множества, когда проще и быстрее работать с обычными массивами или списками, к тому же, во множестве нет возможности получить перечисление вершин в порядке их добавления (особенность хэш-таблицы).

Кстати, сами вершины обычно вообще отдельно не хранятся, а указывается только их количество V, они автоматически принимают номера от 0 до V-1. Для хранения цвета / веса или других характеристик вершин можно использовать параллельные массивы для каждого критерия.

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

Это самый популярный и расточительный способ представления графа в памяти. Его уместно использовать, если количество рёбер велико, порядка V².

Для хранения рёбер используется двумерная матрица размерности [V, V], каждый [a, b] элемент которой равен 1, если вершины a и b являются смежными и 0 в противном случае. 

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

Сложность по памяти: O(V²).

Сложность перечисления всех рёбер: O(V²).

Сложность перечисления всех вершин, смежных с а: O(V).

Сложность проверки смежности вершин a и b: О(1).

Матрица инцидентности

Это самый расточительный способ хранения графа, его уместно использовать, если количество рёбер невелико.

Для хранения используется двумерная матрица размера [V, E], в каждом столбце которой записано одно ребро таким образом: напротив вершин, инцидентных этому ребру, записаны 1, в остальных случаях 0.

Таким образом, сумма чисел в каждом столбце равна 2, а сумма чисел в строчке a равна степени вершины а.

Сложность по памяти: O(V x E).

Сложность перечисления всех рёбер: O(V x E) - хоть каждое ребро и хранится в отдельном столбце, но для получения информации об инцидентных ему вершинах нужно перебрать все числа в столбце.

Сложность перечисления всех вершин, смежных с а: O(V x E).

Сложность проверки смежности вершин a и b: O(E) - достаточно пройтись по строчкам a и b в поисках двух единиц.

Перечень рёбер

Если из матрицы инцидентности убрать все нули, в каждом столбце останется только два числа для каждого ребра - номера инцидентных ему вершин. То есть, для перечисления рёбер достаточно составить список из пар чисел, это очень экономный способ: каждое ребро хранится один раз, когда во всех других вариантах каждое ребро, как правило, записывается дважды.

Недостаток - при поиске вершин в списке рёбер нужно выполнять по две проверки - сравнивать и первую вершину, и вторую.

Сложность по памяти: O(E).

Сложность перечисления всех рёбер: O(E).

Сложность перечисления всех вершин, смежных с а: O(E).

Сложность проверки смежности вершин a и b: О(E).

Список рёбер можно сгруппировать по вершинам, что позволит ускорить поиск смежных вершин. У нас получится ещё три очередных способа, которые очень похожи друг на друга, отличаются лишь способом записи векторов.

Векторы смежности

Для записи вектора смежности используется двумерная матрица размером [V, S], где S - максимальная степень вершины в графе.

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

Сложность по памяти: O(V x S).

Сложность перечисления всех рёбер: O(V x E)

Сложность перечисления всех вершин, смежных с а: O(Sa) (Sa = степень вершины а) = O(E)

Сложность проверки смежности вершин a и b: О(Sa) = O(Sb) = O(E)

Массивы смежности

Для экономии памяти, используется ступенчатый массив, длина каждой строки равна степени данной вершины.

Сложность по памяти: O(сумма степеней всех вершин) = O(E).

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

Здесь используется односвязный список для перечисления всех смежных вершин.

Сложность по памяти: O(V + сумма степеней всех вершин) = O(V + 2xE) = O(V + E)

Структура с оглавлением

Один из самых экономных способов представления графа в памяти. Фактически, мы записываем все массивы смежности в одну строчку, в один линейный массив, и создаём массив-оглавление, с указателями на начало списка для каждой вершины.

Сложность по памяти: O(V + сумма степеней всех вершин) = O(V + E).

Список вершин и список рёбер

Самый экстравагантный способ хранения графа.

Вершины записываются в односвязных список, от каждой вершины есть указатель на список всех рёбер, инцидентных данной вершины. Каждое ребро, в свою очередь, имеет указатель на вторую инцидентную ей вершину и на следующее ребро. 

Получается весьма разветвлённый граф для представления графа.

Сложность по памяти: O(V + сумма степеней всех вершин) = O(V + E).

Сложность перечисления всех рёбер: O(V x E)

Сложность перечисления всех вершин, смежных с а: O(Sa) (Sa = степень вершины а) = O(E)

Сложность проверки смежности вершин a и b: О(Sa) = O(Sb) = O(E)

Теперь, когда мы знаем способы представления графа в памяти компьютера, можем выбирать наиболее приемлемые варианты для каждой конкретной задачи.

На курсе «Алгоритмы и структуры данных» мы рассматриваем следующие алгоритмы в модуле “Теория графов”: поиск вширь и вглубь, топологическая сортировка (Кана, Таряна, Демукрона), поиск компонент сильной связности (Косарайю), поиск минимального скелета (Прима, Краскала, Борувки), поиск кратчайшего пути (Флойда-Уоршалла, Баллмана-Форда, Дейкстры), алгоритм Джонсона для поиск кратчайшего пути в орграфе с отрицательными дугами (см. мою статью), решение задачи коммивояжера (ближайшего соседа, кратчайшего ребра, ближайшего посредника) и вишенка на торте - алгоритм А* звезда поиска кратчайшего пути с эвристической функцией.

Также хочу пригласить всех желающих на бесплатный демоурок по теме «Дерево отрезков - быстро и просто». Зарегистрироваться на урок.