что такое список ребер
Теория графов. Часть третья (Представление графа с помощью матриц смежности, инцидентности и списков смежности)
Все, что познается, имеет число, ибо невозможно ни понять ничего, ни познать без него – Пифагор
Список смежности (инцидентности)
Взвешенный граф (коротко)
Итак, мы умеем задавать граф графическим способом. Но есть еще два способа как можно задавать граф, а точнее представлять его. Для экономии памяти в компьютере граф можно представлять с помощью матриц или с помощью списков.
Матрица является удобной для представления плотных графов, в которых число ребер близко к максимально возможному числу ребер (у полного графа).
Другой способ называется списком. Данный способ больше подходит для более разреженных графов, в котором число ребер намного меньше максимально возможного числа ребер (у полного графа).
Перед чтением материала рекомендуется ознакомится с предыдущей статьей, о смежности и инцидентности, где данные определения подробно разбираются.
Матрица смежности
Но тем кто знает, но чуть забыл, что такое смежность есть краткое определение.
Смежность – понятие, используемое только в отношении двух ребер или в отношении двух вершин: два ребра инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.
Матрица (назовем ее L) состоит из n строк и n столбцов и поэтому занимает n^2 места.
Каждая ячейка матрицы равна либо 1, либо 0;
Ячейка в позиции L (i, j) равна 1 тогда и только тогда, когда существует ребро (E) между вершинами (V) i и j. Если у нас положение (j, i), то мы также сможем использовать данное правило. Из этого следует, что число единиц в матрице равно удвоенному числу ребер в графе. (если граф неориентированный). Если ребра между вершинами i и j не существует, то ставится 0.
Для практического примера возьмем самый обыкновенный неориентированный граф:
А теперь представим его в виде матрицы:
Ячейки, расположенные на главной диагонали всегда равны нулю, потому что ни у одной вершины нет ребра, которое и начинается, и заканчивается в ней только если мы не используем петли. То есть наша матрица симметрична относительно главной диагонали. Благодаря этому мы можем уменьшить объем памяти, который нам нужен для хранения.
С одной стороны объем памяти будет:
Но используя вышеописанный подход получается:
Потому что нижнюю часть матрицы мы можем создать из верхней половины матрицы. Только при условии того, что у нас главная диагональ должна быть пустой, потому что при наличии петель данное правило не работает.
Если граф неориентированный, то, когда мы просуммируем строку или столбец мы узнаем степень рассматриваемой нами вершины.
Если мы используем ориентированный граф, то кое-что меняется.
Здесь отсутствует дублирование между вершинами, так как если вершина 1 соединена с вершиной 2, наоборот соединена она не может быть, так у нас есть направление у ребра.
Возьмем в этот раз ориентированный граф и сделаем матрицу смежности для него:
Если мы работаем со строкой матрицы, то мы имеем элемент из которого выходит ребро, в нашем случаи вершина 1 входит в вершину 2 и 8. Когда мы работаем со столбцом то мы рассматриваем те ребра, которые входят в данную вершину. В вершину 1 ничего не входит, значит матрица верна.
Если бы на главной диагонали была бы 1, то есть в графе присутствовала петля, то мы бы работали уже не с простым графом, с каким мы работали до сих пор.
Матрица инцидентности
Инцидентность – понятие, используемое только в отношении ребра и вершины: две вершины (или два ребра) инцидентными быть не могут.
Матрица (назовем ее I) состоит из n строк которое равно числу вершин графа, и m столбцов, которое равно числу ребер. Таким образом полная матрица имеет размерность n x m. То есть она может быть, как квадратной, так и отличной от нее.
Ячейка в позиции I (i, j) равна 1 тогда, когда вершина инцидентна ребру иначе мы записываем в ячейку 0, такой вариант представления верен для неориентированного графа.
Сразу же иллюстрируем данное правило:
Сумма элементов i-ой строки равна степени вершины.
Одной из особенностей данной матрицы является то, что в столбце может быть только две ненулевых ячейки. Так как у ребра два конца.
Список смежности (инцидентности)
Список смежности подразумевает под собой, то что мы работаем с некоторым списком (массивом). В нем указаны вершины нашего графа. И каждый из них имеет ссылку на смежные с ним вершины.
В виде списка это будет выглядеть так:
Неважно в каком порядке вы расположите ссылку так как вы рассматриваете смежность относительно первой ячейки, все остальные ссылки указывают лишь на связь с ней, а не между собой.
Так как здесь рассматривается смежность, то здесь не обойдется без дублирования вершин. Поэтому сумма длин всех списков считается как:
Когда мы работаем с ориентированным графом, то замечаем, что объем задействованной памяти будет меньше, чем при неориентированном (из-за отсутствия дублирования).
Сумма длин всех списков:
Со списком инцидентности все просто. Вместо вершин в список (массив) вы вставляете рёбра и потом делаете ссылки на те вершины, с которыми он связан.
К недостатку списка смежности (инцидентности) относится то что сложно определить наличие конкретного ребра (требуется поиск по списку). А если у вас большой список, то удачи вам и творческих успехов! Поэтому, чтобы работать максимальной отдачей в графе должно быть мало рёбер.
Взвешенность графа
К примеру, возьмем граф с весами на ребрах:
И сделаем матрицу смежности:
В ячейках просто указываем веса ребра, а в местах где отсутствует связь пишем 0 или -∞.
Более подробно данное определение будет рассмотрено при нахождении поиска кратчайшего пути в графе.
Итак, мы завершили разбор представления графа с помощью матрицы смежности и инцидентности и списка смежности (инцидентности). Это самые известные способы представления графа. В дальнейшем мы будем рассматривать и другие матрицы, и списки, которые в свою очередь будут удобны для представления графа с определёнными особенностями.
Если заметили ошибку или есть предложения пишите в комментарии.
Структуры данных для хранения графов: обзор существующих и две «почти новых»
В этой заметке я решил перечислить основные структуры данных, применяемые для хранения графов в информатике, а также расскажу о еще паре таких структур, которые у меня как-то само собой «выкристаллизовались».
Итак, начнем. Но не с самого начала – думаю, что такое граф и какие они бывают (ориентированные, неориентированные, взвешенные, невзвешенные, с множественными ребрами и петлями или без них), мы все уже знаем.
Итак, поехали. Какие же варианты структур данных для «графохранения» мы имеем.
1. Матричные структуры данных
1.1 Матрица смежности. Матрица смежности представляет из себя матрицу, где заголовки строк и столбцов соответствуют номерам вершин графа, а само значение каждого ее элемента a(i,j) определяется наличием или отсутствием ребер между вершинами i и j (ясно-понятно, что для неориентированного графа такая матрица будет симметрична, ну или же можно договориться, что все значения мы храним лишь выше главной диагонали). Для невзвешенных графов a(i,j) можно задать количеством ребер из i в j (если нет такого ребра, то a(i,j)= 0), а для взвешенных также – весом (суммарным весом) упомянутых ребер.
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 ). Таким образом, для ребра, задаваемого парой вершин под индексами 2i, 2i+1 первого вектора, вес будет равен элементу под индексом i второго вектора.
Ну а зачем это надо?
Ну, автору этих строк для решения ряда задач это показалось достаточно полезным. Ну а с формальной точки зрения, тут будут такие преимущества:
3.2 Ассоциативный массив смежности
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-ю упорядоченными числами). А для графа с нецелочисленными весами ребер признаки можно будет записать в его невзвешенный компонент.
MT1100: Дискретная математика
Помимо геометрического (графического) и аналитического способов задания графов существует еще, как минимум, три эквивалентых им способа.
Матрицей смежности для графа %%G = (V, E)%% называется квадратная матрица %%A = (a_
$$ A = \begin
Матрица смежности для примера из «Основных понятий»
Для того, чтобы список ребер однозначно задавал граф, необходимо помимо списка ребер указать множество всех изолированных вершин этого графа.
| 1 | %%B, C%% |
| 2 | %%A, C%% |
| 3 | %%B, F%% |
| 4 | %%A, F%% |
| 5 | %%A, F%% |
| 6 | %%A, D%% |
| 7 | %%D, F%% |
| 8 | %%D, E%% |
| 9 | %%E, F%% |
| 10 | %%B, E%% |
| 11 | %%E, E%% |
Список ребер для примера из «Основных понятий»
У матрицы инцидентности есть пара особенностей:
$$ B = \begin
Матрица инцидентности для примера из «Основных понятий» с учетом удаления петли у %%E%%
Погружение в графы
Графы в большинстве своем представляют собой неупорядоченные деревья. В основном это утверждение касается ненаправленных и невзвешенных графов. Однако оно остается в силе и в отношении направленных или взвешенных графов, либо направленных и взвешенных одновременно, только при этом надо детализировать понятие “неупорядоченности”.
Направленные графы
Прежде, чем познакомиться с направленным графом, взгляните на ненаправленный граф, представленный ниже:
Ненаправленный граф позволяет свободно перемещаться между вершинами в любом направлении. Теперь посмотрите на направленную версию этого графа:
Тут все меняется. Вы можете перемещаться между вершинами только в направлении стрелки, прикрепленной к каждому ребру. Например, вы можете перейти из пункта А в пункт В, но не из пункта В в пункт А. Немного более строго, верно?
Взвешенные графы
Теперь подумаем о том, чтобы добавить веса ребрам графа. Представьте себе, что у каждого ребра есть цена; цена, которую нужно заплатить, чтобы пересечь ребро. Но перед этим представьте, что все ребра бесплатные, то есть имеют нулевую цену.
На самом деле это мало что меняет, так как с самого начала не было никакой цены, которую нужно было платить. Мы все еще можем пройти по графу без раздумий, если будем следовать указаниям стрелок. Даже если у каждого ребра есть цена, пока все они равны, поскольку каждое ребро имеет одинаковое значение, или вес.
Хорошо, но что, если бы цены были другими? Как бы это изменило способ прохождения по графу?
Поскольку цены теперь отличаются друг от друга, вводится новая динамика. Переход от вершины к вершине будет стоить разных сумм “денег”. Иногда есть только один путь, но в некоторых случаях можно выбрать маршрут, и цена обычно служит определяющим фактором в этом решении. В общем, при переходе из одной вершины графа в другую “самый дешевый” путь является желаемым. Например, если бы я хотел выбрать самый дешевый путь из пункта А в пункт Е, я бы пошел по маршруту АBDЕ. Хотя первоначальным решением мог бы стать маршрут ABE, на самом деле он вышел бы дороже. Подсчеты показывают: стоимость ABE составляет 11, в то время как АBDЕ — всего 9. Надеюсь, вы получили основное представление о взвешенных графах.
До этого момента я называл числа, представляющие каждое ребро, его “ценой”, имея в виду деньги. На самом деле эти цифры обозначают “вес” ребра. Аналогия с деньгами упрощает знакомство с этим видом графа, поскольку деньги — это то, с чем все мы знакомы. Есть и другие способы рассмотрения взвешенного графа. Вы можете представить числа как расстояние между двумя вершинами. Большинство иллюстраций графов не соотнеслись бы с таким представлением, но, тем не менее, такая аналогия тоже приемлема.
Представление графов в коде
Итак, вы уже знаете, что такое направленные и взвешенные графы. Теперь выясним, как представить графы в коде. До сих пор мы использовали только иллюстрации графов. Что ж, оказывается, существует множество способов их представления в коде. Рассмотрим некоторые из них в отношении направленного и невзвешенного графа, показанного ранее.
Список ребер
Список ребер — это именно то, на что похож приведенный ниже код; это список всех ребер на графе. Обратите внимание: каждое ребро представлено своими вершинами — начальной и конечной.
Список смежности
Список смежности — это что-то вроде словаря, в котором каждый ключ является вершиной в графе, а каждое значение — это все, к чему эта вершина примыкает. В направленном графе стрелки должны быть направлены так, чтобы вершина была ключом в списке.
Матрица смежности
Чтобы лучше понять матрицу смежности, изобразим ее в виде рисунка. Если у вас есть опыт работы с матрицами в исчислении, то вам это дастся довольно легко. Если нет, не стоит беспокоиться — всему свое время.
В матрице смежности “0” означает, что две вершины не являются смежными, а “1”, указывает на то, что они являются смежными. Существует множество способов манипулировать такой матрицей и работать с ней, но это выходит за рамки данного объяснения. Обратите внимание на то, что на диагонали есть только нули. Подумайте, почему это так…
Для кодирования матрицы смежности существует несколько способов. В следующих случаях используется ООП:
Когда следует использовать каждый метод
Каждый метод является допустимым представлением графа. Когда же предпочесть один из них всем остальным? Если коротко, то это зависит от того, что вы делаете и как собираетесь манипулировать данными. Например, матрица смежности великолепна и проста в использовании, но может занимать гораздо больше памяти, чем, скажем, список ребер. Обратите внимание и на то, что каждый метод годится для указания веса ребра в случае со взвешенным графом; эта информация была исключена из примеров для упрощения.
Заключение
Мир графов в компьютерных науках огромен. Возможно, для вас это было первое знакомство с ним. Надеемся, что теперь вы лучше сможете понять основы продвижения проектов.
Для дальнейшего погружения в тему рекомендуем изучить алгоритмы обхода, такие как DFS (поиск в глубину) и BFS (поиск в ширину).
Алгоритмы на графах. Алгоритмы обхода графа
Цель лекции: изучить основные алгоритмы обхода графа и научиться решать задачи обхода графа на основе поиска в ширину и поиска в глубину.
Маршрутом в графе называется конечная чередующаяся последовательность смежных вершин и ребер, соединяющих эти вершины.
Маршрут называется открытым, если его начальная и конечная вершины различны, в противном случае он называется замкнутым.
Маршрут называется цепью, если все его ребра различны. Открытая цепь называется путем, если все ее вершины различны.
Замкнутая цепь называется циклом, если различны все ее вершины, за исключением концевых.
Под обходом графов (поиском на графах) понимается процесс систематического просмотра всех ребер или вершин графа с целью отыскания ребер или вершин, удовлетворяющих некоторому условию.
При решении многих задач, использующих графы, необходимы эффективные методы регулярного обхода вершин и ребер графов. К стандартным и наиболее распространенным методам относятся: