Лекция
Привет, сегодня поговорим про представление графов в памяти компьютера, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое представление графов в памяти компьютера, описание бержа графа , список дуг графа, массив дуг графа, списки смежности, матрица инциденций, матрица смежности, хранение графов в памяти эвм , настоятельно рекомендую прочитать все из категории Структуры данных.
Для начала разберемся, что же такое граф и какие они бывают. Граф - множество V вершин и набор E неупорядоченных и упорядоченных пар вершин. Говоря проще, граф - это множество точек (вершин) и соединяющих их путей (дуг или ребер). Граф может быть ориентированным и неориентированным. В ориентированном графе пути (дуги) имеют направление, а в неориентированном - не имеют. Пути в неориентированном графе называются ребрами.
Взвешенным называется такой граф, для каждого ребра(дуги) которого определена некоторая функция. А эта функция называется весовой.
Рассмотрим пример ориентированного взвешенного графа:
Пример ориентированного взвешенного графа
На рисунке точками обозначены вершины графа, стрелками - дуги, черные числа - номера вершин графа, а красные - веса дуг. Вес дуги можно представить также как стоимость. Т.е. например: дан граф, нужно дойти от вершины i до вершины j, заплатив минимальное количество денег/потратив наименьшее количество времени. Пусть в нашем графе, который представлен на рисунке, нам нужно пройти из вершины 5 в вершину 2, а вес дуг - стоимость прохода по данному ребру. В данном примере очевидно, что выгоднее пройти через вершину 1 и только потом прийти в вершину 2, так мы заплатим всего 4 единицы денег, иначе, если пойти напрямую, мы заплатим целых 7 единиц.
Рисунок 1.
На рисунке все смотрится красиво, все задачи вроде бы решаются легко... Но, если граф будет действительно большим, например на 1000 вершин? Да, такой граф на бумажке рисовать очень долго и неприятно... Пускай лучше все это делает за нас компьютер!
Проблема правильного хранения графа в памяти компьютера(ЭВМ) действительно актуальна в сегодняшние дни.
Очертанием графа считается любая топологически связанная область, ограниченная ребрами графа. Для многих приложений все узлы графа должны совпадать с узлами технологической сетки. В этом случае ребра графа могут представлять собой кривые линии, дуги или ломаные линии, состоящие из отрезков прямых.
Важно помнить, что сеть может быть изображена многими различными способами; например, сети, приведенные на рис. 8.20, изоморфные.
Рис. 8.20. Способы изображения сети
Графы в ПЭВМ можно представить тремя способами: матрицей смежности, матрицей инцидентности и вектором смежности.
Известны различные способы представления графов в памяти компьютера, кото рые различаются объемом занимаемой памяти и скоростью выполнения oneраций над графами. Представление выбирается, исходя из потребностей конкретной задачи. Далее приведены четыре наиболее часто используемых представления с указанием характеристики n(р, q) — объема памяти для каждого представления. Здесь р — число вершин, a q — число ребер.
ЗАМЕЧАНИЕ Указанные представления пригодны для графов и орграфов, а после некоторой модификации также и для псевдографов, мультиграфов и гиперграфов.
Представления иллюстрируются на конкретных примерах графа G и орграфа D диаграммы которых представлены на рис. 2.
Рисунок 2. Диаграммы графа (слева) и орграфа (справа), используемых в качестве примеров
Представление графа с помощью квадратной булевской матрицы
М : array [l..p, l..p] of 0..1,
отражающей смежность вершин, называется матрицей смежности, где
если вершина vi смежна с вершиной vj
если вершины vi и vj не смежны.
Для матрицы смежности n(p,q) = О(р2)
Пример
Кроме большого количества требуемой памяти и медленной работы на разреженных графах (графах, у которых E << V2) у матрицы смежности есть еще один важный недостаток. Иногда в задачах нужно выводить не номера вершин, а номера дуг (ребер) на вводе. Хранить эти номера матрица смежности «не умеет». Нужно реализовывать восстановление номера дуги (ребра) как-то иначе, а это совсем неудобно.
Приведем расчеты временной сложности хранения графа матрицей смежности:
Операция Временная сложность
Проверка смежности вершин x и y О(1)
Перечисление всех вершин смежных с x О(V)
Определение веса ребра (x, y) О(1)
Перечисление всех ребер (x, y) О(V2)
Перечисление ребер, инцидентных вершине x Номера ребер не хранятся
Перечисление вершин, инцидентных ребру s Номера ребер не хранятся
Определение веса вершины x О(1)
Выделение памяти под битовую матрицу
Добавления ребра… Куда поставить 1?
Функция печати битовой матрицы
расширение функции main()
На практических занятиях самостоятельно:
1) запустите код и протестируйте его для матриц смежности графов с 32 и более вершинами.
2) допишите функцию удаления ребра между вершинами a и b
Матрица инциденций графа – прямоугольная матрица В с числом строк p и числом столбцов q. Об этом говорит сайт https://intellect.icu . Каждый столбец соответствует одному из ребер. Столбец, соответствующий ребру e = {i, j} содержит 1 в i-й и j-й строке, в остальных строках содержатся нули. Столбец, соответствующий петле, содержит единственную 1. Для орграфа начало и конец дуги задаются разными числами (например, –1 – начало, 1 – конец). Для мультиграфа можно либо рассматривать каждое ребро в составе мультиребра как отдельное (с записью в отдельный столбец), либо записывать значение кратности ребра вместо 1.
Представление занимает объем памяти, равный p*q*a, где a – размер элемента матрицы.
Представление графа с помощью матрицы Н : array [l..p, l..q] of 0..1 (для орграфов H : array [l..p,l..q] of -1..1), отражающей инцидентность вершин и ребер, называется матрицей инциденций, где для неориентированного графа
если вершина vi инцидентна ребру ej
в противном случае,
а для ориентированного графа
если вершина vi инцидентна ребру ej и является его концо
если вершина vi и ребро ej не инцидиентны,
если вершина vi инцидентна ребру ej и является его началом.
Для матрицы инциденций n(p,q)=O(pq).
Примеры матриц инциденций
Пример
Пространственная сложность этого способа O(N*M).
Временные сложности сведены в таблицу
Матрица инцидентности лучше всего подходит для операции «перечисление ребер, инцидентных вершине x».
Массив ребер графа – прямоугольная матрица C с двумя строками и числом столбцов q. Каждый столбец соответствует одному из ребер. В столбце, соответствующем ребру e = {i, j} первый элемент содержит i, а второй – j.
Матрица смежности. Любой граф G = (V, Е) с М вершинами может быть представлен матрицей размера М х М при условии, что вершинам G приписаны произвольные метки. Если вершины G обозначены Vv V2,..., VM, то матрица смежности Л определяется следующим образом:
Здесь К — вес ребра, соединяющего данные вершины. На рис. 8.21 представлены граф и матрица смежности, описывающая его.
Рис. 8.21. Матрица смежности (а) для графа (б)
Матрица смежности неориентированного графа является симметричной.
Матрица инцидентности. Если вершины графа обозначены vp v2, ..., vM, а ребра — метками ер е2,..., eN, то матрица инцидентности Мх Мопределяется следующим образом:
Часто в матрицах смежности и инцидентности вместо нуля ставят « — » (для наглядности). Единицы в матрицах (рис. 8.22) могут быть заменены целыми числами, характеризующими веса ребер, такая матрица называется матрицей оценки (весов).
Рис. 8.22. Матрица инцидентности (инциденций) (а) для графа (б)
На рис. 8.23, 8.24 приведены матрицы инциденций для ориентированного и неориентированного графов.
Модель системы часто представляется ориентированным графом G = (V, Е) с множеством вершин V = vp ...., vn и множеством дуг Е — упорядоченных пар номеров смежных вершин [/, у], Е = [ipjVn,jnl Общее число таких пар обозначим как Q. Одним из способов представления топологии является матрица изо- морфности D, в строках которой помещены номера входящих (с плюсом) и выходящих (с минусом) дуг.
Рис. 8.23. Ориентированный граф и его матрица инциденций
Рис. 8.24. Неориентированный граф и его матрица инциденций
Для графа, приведенного на рис. 8.25, матрицы смежности и изо- морфности имеют вид
Рис. 8.25. Модель системы в форме графа
Избыточность хранимой информации в матрице смежности (нулевые значения) компенсируется простотой вычислительных алгоритмов и скоростью получения требуемой информации из матрицы.
Другой способ представления графа — вектор смежности, выдающий списки узлов, с которыми данный узел связан непосредственно. Для графа, изображенного на рис. 8.26, такое описание можно представить в виде структуры (таблицы). В столбце S представлены
Рис. 8.26. Граф (а), представленный вектором смежности (б)
номера узлов, далее в строке таблицы следует список соседних узлов. По этой причине число столбцов в каждой из строк различно.
Представление древовидных структур. При представлении в машинной памяти древовидных структур в виде связного списка каждый элемент списка может содержать три поля, в одном из которых хранятся данные, соответствующие элементу (базовый тип), а в двух оставшихся полях — указатели левого и правого потомков узла (рис. 8.27).
Рис. 8.27. Представление древовидной структуры: а — дерево; б — табличное представление
Представление графа с помощью списочной структуры, отражающей смежность вершин и состоящей из массива указателей Г : array [l..p] of N на списки смежных вершин (элемент списка представлен структурой N : record v : l..p; n : N endrecord), называется списком смежности. В случае представления неориентированных графов списками смежности n(p,q) = O(p + 2q), а в случае ориентированных графов n(р, q) = О(р + q).
Пример
Списки смежности для графа G и орграфа D представлены на рис. 3
Рисунок 3 . Списки смежности для графа G (слева) и орграфа D (справа)
Приведем расчеты временной сложности хранения графа списками смежных вершин:
Времена у всех операций, вроде бы, такие же, как и у списка ребер. Однако, большинство из них реально намного меньше. Например, проверка смежности вершин x и y и перечисление всех вершин смежных с x в списке ребер гарантированно будет выполнятся О(Е) операций, т.к. нам обязательно нужно пробежать весь список, а в списке смежности мы бежим только по вершинам, смежным с х.
Кроме того, мы экономим колоссальное количество памяти.
Реализация списков смежности на C++
Односвязные списки, построенные при помощи структур
Следующий тип хранения графа в памяти компьютера - список дуг. Чаще всего это двумерный массив размером 3*E, в первой строке которого хранится информация, из какой вершины начинается дуга, во второй - в какой кончается, а в третьей строке - вес дуги. Опять же разберемся на примере
1 2 3 4 5 6
1 1 2 3 4 5 5
2 2 3 4 2 1 2
3 1 2 3 4 3 7
Мы четко видим, что почти вся таблица заполнена "нужными" значениями, а не нулями. Это уже хорошо, значит, память экономится.
Представление графа с помощью массива структур E: array [1..p] of record b,e: 1..p endrecord, отражающего список пар смежных верщин, называется массивом ребер (или, для орграфов, массивом дуг). Для массива ребер (или дуг) n(p,q)=O(2q).
Пример
Представление с помощью массива ребер (дуг) показано в следующей таблице (для графа G слева, а для орграфа D справа).
Приведем расчеты временной сложности хранения графа списком дуг:
Операция Временная сложность
Проверка смежности вершин x и y О(E)
Перечисление всех вершин смежных с x О(E)
Определение веса ребра (x, y) О(E)
Перечисление всех ребер (x, y) О(E)
Поиск i-ой дуги О(1)
Как видно, этот способ, в отличие от матрицы смежности, хранит информацию о номере дуги. Также ясно, что этот способ нам выгоден, если чаще всего нам нужно будет узнать что-то (вес, вершины начала или конца) о i-ой дуге. Однако, такие задачи в практическом программировании встречаются довольно редко.
Если в предыдущих представлениях одно ребро мы заменяли двумя дугами, то список дуг может хранить или дуги или ребра (в зависимости от реализации). Это довольно удобно и может требовать в 2 раза меньше памяти.
Для того чтобы ускорить работу матрицы смежности на разреженных графах, можно использовать другой тип хранения графа - описание Бержа. Для каждой вершины хранится список смежных вершин. Чаще всего для этого используется двумерный массив размером V в квадрате, в строке u которого хранятся номера вершин, смежных с u. В нулевой элемент строки u вписывается количество вершин, хранящихся в данной строке. Теперь попробуем представить наш граф при помощи описания Бержа на примере:
0 1 2 3 4 5 6
1 1 2 0 0 0 0 0
2 1 3 0 0 0 0 0
3 1 4 0 0 0 0 0
4 1 2 0 0 0 0 0
5 2 1 2 0 0 0 0
6 0 0 0 0 0 0 0
В нулевом столбце хранятся "длины" строк. Однако, вес дуг никак не хранится, а если его хранить отдельно, то нужно заводить еще один массив размером V в квадрате...
Временные сложности сведены в таблицу:
Для неориентированных графов определено только FO-представление, реализуемое одним одномерным массивом.
Длина массива FO: 1 + 2·q + p, где q – количество ребер, а p – количество вершин графа
Если нумерация вершин начинается с нуля, роль разделителя играет другой символ, например -1.
пример реализации на C++
Варианты для орграфа:
1. для каждой вершины записываются номера вершин, в которые из этой вершины исходят дуги (FO-представление),
2. Для каждой вершины записываются номера вершин, из которых исходят дуги в эту вершину (FI-представление)
Длина массивов FO и FI равна 1 + q + p.
Задание на 5 минут: Напишите FO и FI представления для этого орграфа. В качестве разделителя используйте ноль
Ответ
Для неориентированных графов определено только MFO-представление.
Длина массива ME равна 2 · q.
Длина массива MV равна p + 1
Пример реализации
Варианты для орграфа:
1. FO-представление записывается в виде двух массивов (выходящие ребра)
2. FI-представление записывается в виде двух массивов (входящие ребра)
Для неориентированных графов допустимы сокращенные FO- и MFO представления (BFO и BMFO)
В массивы FO и ME для каждой вершины записываются только те номера вершин, которые не меньше (или не больше) номера этой вершины.
Это позволяет уменьшить размер массива FO c (1+2*q+p) до (1+q+p), а массива ME – с 2*q до q.
пример
Объектно-ориентированная библиотека для работы с графами
Boost Graph Library (BGL). Graph interface
Найти универсальный способ хранения графа в памяти компьютера, который бы хранил максимально много информации о графе, работал с любыми графами и работал бы быстроне простая задача, универсального способа нет. Для различных задач и графов оптимальны различные представления. Конечно, наиболее мощным и универсальным способом хранения является список смежности. зачастую он работает быстрее и все еще требует не так уж и много памяти. Однако, если количество дуг приближается к квадрату количества вершин, то лучше матрицы смежности способа не найти, т.к. тогда скорость работы и количество памяти даже списка смежности приближается к матрице смежности, если не требует больше... Конечно, можно написать и список смежности, однако пишется он дольше матрицы смежности, да и работать с матрицей смежности намного проще.
Применение матрицы смежности является оправданным, когда:
1) число вершин невелико (p <=1000), а число ребер велико (стандартная оценка для обыкновенного графа: > p(p-1)/4);
2) когда необходимо иметь быстрый доступ к произвольным ребрам графа;
3) когда часто необходимо добавлять и удалять ребра при неизменном числе вершин.
Когда трансформация графа не требуется, хорошим компромиссом для графов общего вида является MFO-представление и его варианты (списки смежности
и др.).
Матрица инциденций – самое невыгодное с алгоритмической точки зрения представление графа.
Сравнение сложностей базовых операций при различных представлениях графа
На этом все! Теперь вы знаете все про представление графов в памяти компьютера, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое представление графов в памяти компьютера, описание бержа графа , список дуг графа, массив дуг графа, списки смежности, матрица инциденций, матрица смежности, хранение графов в памяти эвм и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Структуры данных
Комментарии
Оставить комментарий
Структуры данных
Термины: Структуры данных