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

Всем привет.

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

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

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

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
Share post
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 14

    +3
    Было бы здорово дополнить все это сравнением эффективности выполнения разных операций над графом в зависимости от способа его хранения.
      0
      В свое время мы хранили узлы графов в виде структур, с указателями на связанные узлы. И графы были разных размеров.
      При чем, узлы могли быть связаны в связке 1 к 1, 1 к 2, 1 к 3 (на самом деле сколь угодно связанных соседей).
      А хранились в файлы с помощью id. У каждого узла свой уникальный id. В файле сохраналясь информация об узле, его id, а так же id связанных соседних узлов.
      При загрузке считывались все узлы, создавалась хеш таблица <id, node_ptr>, а потом во второй проход по каждому узлу считывались id привязанных узлов и из хеш таблицы быстро получали указатель на нужный узел и запоминали его в текущем. Просто и быстро.
        0
        А чем вектор смежности отличается от списка ребер?
          0
          В чем-то оный и есть — но в одном векторе.
          В расширенном же варианте — еще и с дополнительными свойствами ребер.
          Как говорится, "… в развитие классических списков ребер..."
            0
            ИМХО развитием это назвать сложно. Вместо массива типизированых ребер — массив целых чисел, который хранит те же данные таким же образом. По сути делаем код менее читабельным без никакого выигрыша.
          0
          Матрица смежности годится для маленьких графов и алгоритмов вроде Флойда-Уоршала, а для всего остального списки смежности всё решают. В ребре можно хранить любую информацию, плюс можно использовать индекс (например, если вершины имеют произвольные метки или если нужен быстрый доступ к ребру).
            0
            Про роутинг по графу в базе данных здесь.
              0
              Как хранить графы с весами в приведённых структурах?
              Деревья не являются подходящей для хранения графов структурой? По ощущениям, это первая структура, в которой захочется хранить граф, а не массив рёбер.
                0
                Ну вообще кратко я коснулся по каждой структуре данных, где там хранят веса ребер. Давайте с примерами.

                По вектору смежности — это случаи а2 и б.
                Если ребра целочислены (случай а2), то это просто каждое третье число. Например, по графу 1->2:2, 2->3:-1, 3->1:6 4->4:5 это будет просто std::vector = {1,2,2, 2,3,1, 3,1,6, 4,4,5}
                Для того же графа по ассоциативному массиву смежности будет std::map <std::pair < int, int>, int> (ну или же multimap), где ключи — пара номеров вершин, а значение — длина ребра.

                Если ребра — нецелочислены (случай б), то вектор смежности графа будет храниться в паре векторов std::pair < std::vector, std::vector>, где в первом векторе — сами ребра (каждое ребро задается парой соответствующих вершин), а во втором — их длины.
                Т.обр., для графа 1->2:0.2, 2->3:-0.1, 3->1:0.6 4->4:0.5 у нас будет std::pair < std::vector, std::vector> (первый вектор: {1,2,2,3,3,1,4,4}, а второй: {0.2, -0.1, 0,6, 0.5})

                Для ассоциативного массива смежности — аналогично случаю с целочисленными, только у нас будет std::map <std::pair < int, int>, double> (ну или, опять же, multimap)

                Ну а про другие структуры данных — подробнее с примерами можно посмотреть, например, по ссылкам к заметке (4; 5). так, в частности, для матрицы смежности вес ребра из вершины i в вершину j может быть задан как раз элементом матрицы a(i, j). И т.д.

                +2

                Я как-то использовал списки смежности но очень по хитрому. Задача хранить узлы и ребра с мета информацией. Идея такая:


                • узлы и ребра имеют одинаковый размер. Это позволяет выделять элементы сегментами по фиксированому поличеству как массивы. Что позволяет получать доступ к любому элементу за О(1).
                • в моем случае ребра могут соединять не только узлы. Начальным/конечным элементом для ребра может быть не только узел, но и другое ребро.
                • соответственно каждый элемент имеет ссылку на первое ребро в списке смежности входящих и отдельно ссылку на первый элемент в списке выходящих ребер. По сути ссылка это адрес 32 бита, в котором старшие 16 бит указывают на номер сегмента, а младшие 16 бит на индекс элемента в сегменте. Опять доступ за О(1).
                • чтобы не хранить списки смежности отдельно они запрятаны в ребра, которые хранятся в сегментах. Каждое ребро имеет ссылку (32 бит) на следующий и предыдущий элемент в списке смежности входящих и выходящих ребер для исходного и конечного элементов (может картинка внесет ясность):

                И так получается что вставка ребер очень быстрая, как вставка в обычный двунаправленный список. Удаление также. И все быстро работает за счет доступа к любому элементу за О(1), если не учитывать блокировки и т. д… Это отдельная история.


                Вот ссылка на структуры данных в коде:
                https://github.com/deniskoronchik/sc-machine/blob/dev/sc-memory/sc-core/sc-store/sc_element.h


                Вот код создания новой дуги (ребра):
                https://github.com/deniskoronchik/sc-machine/blob/dev/sc-memory/sc-core/sc-store/sc_storage.c#L645-L766

                  0
                  Интересный подход.
                  А про «в моем случае ребра могут соединять не только узлы» подробнее не расскажете?
                    0

                    Да, конечно. У нас используется семантическая сеть, которая построена на основе теории множеств. Базовым кирпичем такой теории является отношение которое связывает множество с его элементов. Это базовая дуга. Поэтому например есть множество отношенией, элементами которого являются подмножества разных отношений, например отношение "быть изображением чего либо". Оно задается узлом в графе (сем. сети). Этот узел обозначает множество всех экземпляром такого отношения. Экземпляром такого отношения является другая дуга, которая обозначает конкретное отношение такого типа. Вот пример:
                    image


                    Немного дополнительных подробностей есть тут: https://habr.com/ru/post/328238/


                    В реализации все просто, все можно соединить со всем с помощью дуг/ребер

                  0
                  Неплохая статья, спасибо =) Мне такая информация как раз нужна
                    0
                    И небольшое дополнение.
                    При использовании ассоциативных массивов смежности для хранения графов с множественными петлями и ребрами можно использовать не только multimap, но и map, если применить подход «расширенных ассоциативных массивов смежности» (раздел 4).
                    Итак, если есть граф 1->2:2, 1->2:-1, то можно задать его так:
                    std::map <std::pair < int, int>, std::vector >: ключ std::pair < int, int> (1, 2) — значение std::vector — {2, -1}.
                    Как выяснилось, удобно.

                    Only users with full accounts can post comments. Log in, please.