2. Представление графов в памяти эвм

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

Матрицей смежности графа 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

0	1	0	1
1	0	1	1
0	1	0	1
1	0	0	0

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

Матрицей инцидентности графа 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	0	0	0
1	0	-1	-1	0
0	0	1	0	-1
0	1	0	1	1

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

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

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

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

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

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

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

	10	12		30					
			10		10				
			10		20				
						10		15	
						8	10		
						8	10		
									10
									9
									5
									

Для нахождения вершин, смежных 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 ячеек памяти.

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
V	10	12	30	10	10	10	20	10	15	8	10	8	10	10	9	5
S	2	3	5	4	6	4	6	7	9	7	8	7	8	10	10	10
U	1	4	6	8	10	12	14	15	16	16
Рис.2.1. Упаковка матрицы весов (табл. 2.3) в список гнездового типа

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

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

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

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

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

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

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
I	1	1	1	2	2	3	3	4	4	5	5	6	6	7	8	9
J	2	3	5	4	6	4	6	7	9	7	8	7	8	10	10	10
V	10	12	30	10	10	10	20	10	15	8	10	8	10	10	9	5
I - начальная вершина, J – конечная вершина, V – вес дуги (I,J)
Рис.2.3. Список рёбер графа, изображенного на рис.1.6

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

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

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

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

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