Учебное пособие Самара 2015 + 004. 43 Ббк 32. 973 Н 19

Способы представления графов

Рассмотрим способы представления графов в памяти ЭВМ. Граф является топологической абстракцией, предназначенной для описания некоторых топологических свойств самых разных объектов и отношений между этими объектами. Существует большое число типов графов, отличающихся классификацион- ными признаками. Такое многообразие обусловлено различными свойствами графов. Так, графы могут быть связными, слабосвяз-

НЫМИ, СИЛЬНОСВЯЗНЫМИ, ПОЛНОСВЯЗНЫМИ, Н СВЯЗНЫМИ, О]ЭИ НТИЈЭ O-
ванными, неориентированными, взвешенными, контурными, бес- контурными, содержащими петли или кратные рёбра (псевдогра- фами), мультиграфами, гиперграфами и т.п. [2, 9].
Для графов имеется большое число алгоритмов обработки данных, например, поиск вершин в графе, поиск кратчайших пу- тей, построение деревьев на графах, очерёдность обхода вершин



Для работы с графом он должен быть каким-либо образом представлен в памяти ЭВМ. Способ представления зависит от ха- рактера решаемых на графе задач. Существует несколько спосо- бов отображения графа на память машины, каждый из которых обладает собственными достоинствами и недостатками [9]. Су- ществуют также и алгоритмы преобразования этих способов опи- сания графа друг в друга [10].

1. 
   Список рёбер
   

Одним из наиболее простых способов является представление графа в виде списка рёбер, соединяющих вершины. Например, для графа, показанного на рисунке 11.1, этот список может вы- глядеть следующим образом:

(1, 2), (1, 3), (1, 4), (2, 4), (3, 4).

145

Рис.11.1 Простой ненаправленный циклический граф

Достоинством такого способа является его простота, а также способность представлять графы практически любых видов. На- пример, в случае ориентированного графа направление ребёр за- даётся порядком указания вершин. Такой граф показан на рисун- ке 11.2.

(1, 2), (1, 3), (1, 4), (4, 2), (4, 3)

Рис. 11.2 — Простой направленный циклический граф и его спи-

сок рёбер

Этот же способ подходит и для описания взвешенных графов, графов с петлями, мультиграфов и т.п. Например, взвешенный направленный циклический граф, показанный на рисунке 11.3, описывается следующим списком рёбер:

(1, 2, 0.20), (1, 3, 0.30), (1, 4, 0.10), (4, 2, 0.33), (4, 3, 0.15).

146

0.20 030

0.10

0.33 0.15
Рис. 11.3 — Взвешенный направленный циклический граф

Список рёбер для графа из М ребер требует в расчёте на вершину объём памяти, пропорциональный 2M. Для получения списка рёбер, непосредственно связанных с текущей вершиной требуется М шагов.

Под термином «список» во всех рассмотренных случаях следует понимать как массив однотипных элементов (в более простом случае), так и связный список в том числе, и даже древо- видную структуру данных. Наряду с простотой, рассматривае- мый способ описания графа обладает, по крайней мере, двумя особенностями, которые при определённых обстоятельствах можно посчитать недостатками. Эти особенности следующие:
порядок перечисления рёбер в списке в общем случае может быть произвольным. Это следует из самой приро- ды графа, когда точно расположение вершин не важно, важны лишь их взаимное расположение и связи между ними. В то же время возможны ситуации, когда отсутст- вует какой-либо логический порядок в перечислении pë- 6ep, что может привести к ухудшению понимания струк- туры графа, а также к усложнению алгоритмов его обра- ботки;

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

147
дёт к усложнению алгоритмов обработки графа.

Рассмотрим другой способ описания графа. Представим граф, как список вершин, для каждой из которых указаны все другие вершины, с которыми текущая соединена рёбрами. Для ненаправленного графа, показанного на рисунке 11.1, список вершин будет следующим:

(1, 2, 3, 4), (2, 1, 4), (3, 1, 4), (4, 1, 2, 3).

В каждом элементе этого списка первой указывается текущая вершина.

Направленный граф, показанный на рисунке 11.2, описыва- ется следующим списком вершин:
(1, 2, 3, 4), (2), (3), (4, 2, 3).

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

Список вершин легко адаптируется к случаю взвешенного графа (рисунок 11.3):
(1, [2, 0.20], [3, 0.30], [4, 0.10] ), (2), (3), (4, [2, 0.33], [3, 0.15] ).

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

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

148
Часто списки инцидентности строят на основе связных спи— сков. Такой способ построения показан на рисунке 11.4.

nil

пil

1 23 nil 2
3 23 nil 4

4
5	nil

6 nil
6

Рис. 11.4 — Список инцидентности направленного графа

Для списков инцидентности справедливо то же ограниче- ние, что и для списков вершин — если исходной структурой дан- ных является массив, то такой список подходит для описания только статических графов или графов с постоянным числом вершин. Для списка рёбер постоянным является число рёбер. Для описания динамического графа в качестве исходной структуры данных необходимо использовать связный список. Каждое звено такого списка будет точкой начала ещё одного списка, в котором указываются вершины, смежные с текущей. В этом случае требу- ется объём памяти, пропорциональный сумме M+N.

3.