Структуры данных для хранения графов: обзор существующих и две «почти новых»

Всем привет.

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

Итак, начнем. Но не с самого начала – думаю, что такое граф и какие они бывают (ориентированные, неориентированные, взвешенные, невзвешенные, с множественными ребрами и петлями или без них), мы все уже знаем.

Итак, поехали. Какие же варианты структур данных для «графохранения» мы имеем.

1. Матричные структуры данных

1.1 Матрица смежности. Матрица смежности представляет из себя матрицу, где заголовки строк и столбцов соответствуют номерам вершин графа, а само значение каждого ее элемента a(i,j) определяется наличием или отсутствием ребер между вершинами i и j (ясно-понятно, что для неориентированного графа такая матрица будет симметрична, ну или же можно договориться, что все значения мы храним лишь выше главной диагонали). Для невзвешенных графов a(i,j) можно задать количеством ребер из i в j (если нет такого ребра, то a(i,j)= 0), а для взвешенных также – весом (суммарным весом) упомянутых ребер.

1.2 Матрица инцидентности. В этом случае наш граф также хранится в таблице, в которой, как правило, номерам строк соответствуют номера его вершин, а номерам столбцов – предварительно занумерованные ребра. Если вершина и ребро инцидентны друг другу, то в соответствующей ячейке записывается ненулевое значение (для неориентированных графов записывается 1 в случае инцидентности вершины и ребра, для ориентированных – «1», если ребро «выходит» из вершины и «-1», если оно в нее «входит» (запоминается достаточно легко, ведь знак «минус» тоже как бы «входит» в число «-1»)). Для взвешенных же графов опять же вместо 1 и -1 можно указывать суммарный вес ребра.

2. Перечислительные структуры данных

2.1 Список смежности. Ну тут, вроде бы, все просто. Каждой вершине графа можно, в общем случае, поставить в соответствие любую перечислительную структуру (список, вектор, массив, …), в которой будут храниться номера всех вершин, смежной данной. Для ориентированных графов будем заносить в такой список лишь те вершины, в которые есть «направленное» ребро из вершины-признака. Для взвешенных графов реализация будет более сложной.

2.2 Список ребер. Довольно популярная структура данных. Список ребер, как подсказывает нам Капитан Очевидность, и представляет собой собственно список ребер графа, каждое из которых задается начальной вершиной, конечной вершиной (для неориентированных графов здесь порядок следования не важен, хотя для унификации можно использовать различные правила, например, указывать вершины в порядке возрастания) и весом (только для взвешенных графов).

Про перечисленные выше списки-матрицы можно подробнее (и с иллюстрациями) посмотреть, например, тут.

2.3 Массив смежности. Не самая часто встречающаяся структура. По своей сути, он представляет собой форму «упаковки» списков смежности в одну перечислительную структуру (массив, вектор). Первые n (по числу вершин графа) элементов такого массива содержат стартовые индексы данного же массива, начиная с которых в нем подряд записаны все вершины, смежные данной.

Вот здесь я нашел самое понятное (для себя) объяснение: ejuo.livejournal.com/4518.html

3. Вектор смежности и Ассоциативный массив смежности

Оно так вышло, что автор этих строк, не являясь профессиональным программистом, однако периодически имевший дело с графами, чаще всего имел дело со списками ребер. Действительно, удобно, если в графе есть множественные петли и ребра. И вот, в развитие классических списков ребер, предлагаю уделить внимание и их «развитию/ ответвлению/ модификации/ мутации», а именно: вектору смежности и ассоциативному массиву смежности.

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

Случай (а1): невзвешенный граф

Будем называть вектором смежности для невзвешенного графа упорядоченный набор четного количества целых чисел (а[2i], a[2i+1],…, где i нумеруется c 0), в котором каждая пара чисел а[2i], a[2i+1] задает ребро графа между вершинами а[2i] и a[2i+1] соответственно.
Данный формат записи не содержит сведений, является ли граф ориентированным (возможны оба варианта). При использовании формата для орграфа считается, что ребро направлено из а[2i] в a[2i+1]. Здесь и далее: для неориентированных графов, при необходимости, могут применяться требования к порядку записи вершин (например, чтобы первой шла вершина с меньшим значением присвоенного ей номера).

В C++ вектор смежности целесообразно задавать с помощью std::vector, отсюда и было выбрано название данной структуры данных.

Случай (а2): невзвешенный граф, веса ребер целочисленные

По аналогии со случаем (а1) назовем вектором смежности для взвешенного графа с целочисленными весами ребер упорядоченный набор (динамический массив) чисел (а[3i], a[3i+1], a[3i+2],…, где i нумеруется c 0), где каждый «триплет» чисел а[3i], a[3i+1], a[3i+2] задает ребро графа между вершинами под номерами а[3i] и a[3i+1] соответственно, а значение a[3i+2] есть вес этого ребра. Такой граф также может быть как ориентированным, так и нет.

Случай (б): невзвешенный граф, веса ребер нецелочисленные

Виду того, что в одном массиве (векторе) нельзя хранить разнородные элементы, то возможна, например, следующая реализация. Граф хранится в паре векторов, в которой первый вектор является вектором смежности графа без указания весов, а второй вектор содержит соответствующие веса (возможная реализация для C++: std::pair<std::vector, std::vector>). Таким образом, для ребра, задаваемого парой вершин под индексами 2i, 2i+1 первого вектора, вес будет равен элементу под индексом i второго вектора.

Ну а зачем это надо?

Ну, автору этих строк для решения ряда задач это показалось достаточно полезным. Ну а с формальной точки зрения, тут будут такие преимущества:

• Вектор смежности, как и любая другая «перечислительная» структура, достаточно компактна, занимает меньше памяти, чем матрица смежности (для разреженных графов), относительно просто реализуется.
• Вершины графа, в принципе, могут быть промаркированы и отрицательными числами. Вдруг да понадобится и такой «изврат».
• Графы могут содержать множественные ребра и множественные петли, причем с разными весами (положительные, отрицательные, даже нулевые). Никаких ограничений тут нет.
• А еще ребрам можно присваивать разные свойства – но об этом см. п. 4.

Однако, надо признать, быстрого доступа к ребру данная «спискота» не подразумевает. И здесь на помощь спешит Ассоциативный массив смежности, о чем – ниже.

3.2 Ассоциативный массив смежности

Итак, если для нас доступ к конкретному ребру, его весу и иным свойствам является критичным, а требования к памяти не позволяют использовать матрицу смежности, то давайте подумаем, как можно изменить вектор смежности, чтобы решить данную задачу. Итак, ключом является ребро графа, которое можно задать в виде упорядоченной пары целых чисел. На что же это похоже? Уж не на ключ ли в ассоциативном массиве? А, если так, почему бы нам это и не реализовать? Пусть у нас появится такой ассоциативный массив, где каждому ключу – упорядоченной паре целых чисел – будет поставлено в соответствие значение – целое или вещественное число, задающее вес ребра. В C++ реализовывать данную структуру целесообразно на базе контейнера std::map (std::map <std::pair < int, int>, int> или std::map <std::pair < int, int>, double>), либо std::multimap, если предполагаются множественные ребра. Ну и вот, и у нас получилась структура для хранения графов, которая занимает меньше памяти, нежели «матричные» структуры, может задавать графы со множественными петлями и ребрами и даже не имеющая жестких требований к неотрицательности номеров вершин (не знаю, кому это надо, но все же).

4. Структур данных хоть «залейся», а чего-то не хватает

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

Итак, пусть у нас имеется невзвешенный граф, для каждого ребра которого необходимо хранить, например, 2 дополнительных признака, задаваемых целыми числами. В этом случае возможно задать его вектор смежности как упорядоченный набор не «пар», а «квартетов» целых чисел (а[2i], a[2i+1], a[2i+2], a[2i+3]…), где a[2i+2] и a[2i+3] и будут определять признаки соответствующего ребра. Для графа же с целыми весами ребер порядок, в целом, аналогичен (отличием будет являться лишь то обстоятельство, что признаки будут следовать после веса ребра и задаваться элементами a[2i+3] и a[2i+4], а само ребро будет задаваться не 4-мя, а 5-ю упорядоченными числами). А для графа с нецелочисленными весами ребер признаки можно будет записать в его невзвешенный компонент.

При использовании ассоциативного массива смежности для графов с целочисленными весами ребер возможно в качестве значения задавать не отдельное число, а массив (вектор) чисел, задающих, помимо веса ребра, все его прочие необходимые признаки. При этом неудобством для случая нецелочисленных весов будет являться необходимость задания признака числом с плавающей запятой (да, это неудобство, но если таких признаков не так и много, и если не задавать их слишком «хитрыми» double, то оно, может, и ничего). И значит, в C++ расширенные ассоциативные массивы смежности могут задаваться следующим образом: std::map <std::pair < int, int>, std::vector> или std::map <std::pair < int, int>, std::vector, при этом первым значением в «векторе-значении-по-ключу» будет вес ребра, а далее располагаются численные обозначения его признаков.

Литература:

Про графы и алгоритмы вообще:

1. Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клиффорд. Алгоритмы: построение и анализ, 2-е издание: Пер. с англ. – М.: Издательский дом «Вильямс», 2011.
2. Харари Фрэнк. Теория графов. М.: Мир, 1973.
Доклад автора про эти самые вектор и ассоциативный массив смежности:
3. Черноухов С.А. Вектор смежности и ассоциативный массив смежности как способы представления и хранения графов / S.A. Chernouhov. Adjacency vector and adjacency map as data structures to represent a graph // Сборник статей Международной научно-практической конференции «Проблемы внедрения результатов инновационных разработок и пути их решения» (Саратов, 14.09.2019 г.). – Стерлитамак: АМИ, 2019, с. 65-69
Полезные интернет-источники по теме:
4. prog-cpp.ru/data-graph
5. ejuo.livejournal.com/4518.html

Источник: habr.com