Представление графов в памяти ЭВМ

Любой граф может быть представлен в матричной форме.

Матрицей смежности графа G=(V,E) называется матрица A порядка n´n, где n=|V|. Элемент матрицы смежности а_ij=1, если (v_i,v_j)ÎЕ, v_i,v_jÎV и a_ij=0, если (v_i,v_j)ÏЕ.

Для графа, изображенного на рис. 1.5, матрица смежности представлена в таблице 2.1.

Таблица 2.1. Матрица смежности графа, изображенного на рис.1.5

Отметим, что для неориентированных графов матрица смежности симметрична относительно главной диагонали, то есть в памяти ЭВМ достаточно хранить только половину матрицы.

Матрицей инцидентности графа G=(V,E) называется матрица B порядка n´m, где n=|V|, m=|E|. Элементы матрицы инцидентности b_ij определяются следующим образом: b_ij=1, если i-я вершина является началом j-ой дуги, b_ij=-1, если i-я вершина является концом j-ой дуги, b_ij=0, если i-я вершина и j-я дуга не инцидентны.

Для неориентированных графов в матрице инцидентности элементам достаточно присваивать только два символа (1 и 0).

Для графа, представленного на рис. 1.4, матрица инцидентности показана в таблице 2.2.

Таблица 2.2. Матрица инцидентности графа, изображенного на рис.1.4

-1	-1
		-1	-1
				-1

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

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

Матрица весов для графа, представленного на рис.1.6, приведена в таблице 2.3.

На практике очень часто матрицы, представляющие графы, бывают сильно разряженными, то есть содержат много символов “0” или “¥”. Это приводит к неоправданным затратам памяти при хранении этих матриц в ЭВМ.

Объем памяти можно существенно уменьшить, если упаковывать матрицы в списки гнездового типа.

Пример упаковки рассмотренной матрицы весов (табл. 2.3) в список гнездового типа, реализованный на трех векторах (массивах), приведен на рис. 2.1.

Таблица 2.3. Матрица весов графа, изображенного на рис.1.6

¥			¥		¥	¥	¥	¥	¥
¥	¥	¥		¥		¥	¥	¥	¥
¥	¥	¥		¥		¥	¥	¥	¥
¥	¥	¥	¥	¥	¥		¥		¥
¥	¥	¥	¥	¥	¥			¥	¥
¥	¥	¥	¥	¥	¥			¥	¥
¥	¥	¥	¥	¥	¥	¥	¥	¥
¥	¥	¥	¥	¥	¥	¥	¥	¥
¥	¥	¥	¥	¥	¥	¥	¥	¥
¥	¥	¥	¥	¥	¥	¥	¥	¥	¥

Для нахождения вершин, смежных i–ой вершине, и весов соответствующих дуг по такой структуре необходимо вычислить начальный In и конечный Ik индексы в векторах V и S по формулам

In=U_i

Ik=U_i+1-1.

Тогда S_In,S_In+1,…,S_Ik - вершины, смежные i-ой вершине, V_In,V_In+1,…,V_Ik – длины дуг (i,S_In),(i,S_In+1,),…,(i,S_Ik).

Для хранения упакованной таким образом матрицы весов понадобится 42 ячейки памяти, занимаемых массивами V,S и U. Неупакованная матрица занимала 10´10=100 ячеек памяти.

V

S

U

Рис.2.1. Упаковка матрицы весов (табл. 2.3) в список гнездового типа

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

Для графа, изображенного на рис. 1.6, список смежности представлен на рис. 2.2.

Еще один способ хранения графов - это список рёбер, то есть список, в котором перечислены все рёбра графа.

Список рёбер графа, представленного на рис. 1.6, приведен на рис. 2.3.

Список рёбер реализован на трех массивах и занимает 48 ячеек. Можно также вместо массивов использовать списковые структуры.

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

I

J

V

I - начальная вершина, J – конечная вершина, V – вес дуги (I,J)

Рис.2.3. Список рёбер графа, изображенного на рис.1.6

Упражнение. Постройте алгоритмы для преобразования друг в друга всех пар следующих представлений графа:

а) матрица смежности;

б) список рёбер;

в) список смежности;

г) матрица инцинденций.