2.4.8.Некоторые сд для хранения графов и деревьев

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

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

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

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

Таблица 2.4.
Матрица смежности графа, изображенного на рис.2.17
0	1	0	0
0	0	1	1
0	0	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).

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

Таблица 2.5.
Матрица инцидентности графа, изображенного на рис.2.17
1	0	0	0	-1
-1	1	1	0	0
0	-1	0	1	0
0	0	-1	-1	1

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

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

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

Объем памяти можно существенно уменьшить, если упаковывать матрицы в массивы смежности. Пример упаковки рассмотренной матрицы весов (табл. 2.6) в массивы приведен на рис. 2.19.

Упаковка осуществляется с помощью трех массивов: S, V и U. Заполнение массивов S и V осуществляется путем построчного просмотра матрицы. При просмотре текущей строки матрицы в массиве S сохраняются номера столбцов, содержащие значения, отличные от , сами значения сохраняются в массиве V. Массив U служит для разграничения информации в массивах S и V, i-ый элемент массива U содержит индекс массивов S и V, с которого начинается информация, относящаяся к i-ой строке матрицы. Таким образом, для нахождения вершин, смежных 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). Если Ik=U_i+1-1 окажется меньше In=U_i, то это означает, что i-я строка матрицы весов содержит одни , т.е. i-я вершина не имеет смежных вершин.

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

Если упаковывается матрица смежности, то массив V не нужен.

Таблица 2.6.
Матрица весов графа, изображенного на рис.2.18
	10	12		30					
			10		10				
			10		20				
						10		15	
						8	10		
						8	10		
									10
									9
									5
									

	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	17	17
Рис.2.19. Упаковка матрицы весов (табл. 2.6) в массивы смежности

Еще один способ хранения графов - это массив рёбер, то есть массив записей, в котором перечислены все рёбра графа (каждая запись кодирует ребро). Массив рёбер графа, представленного на рис. 2.18, приведен на рис. 2.20. Здесь массив занимает 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.20. Список рёбер графа, изображенного на рис.2.18

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

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

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

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

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

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

Например, дерево, изображенное на рис.2.23, может быть сохранено матрицей смежности, представленной в табл.2.7. К недостаткам такого способа следует отнести то, что получаемые матрицы, как правило, сильно разряженные, и занимают большой объем памяти. Как было сказано выше, объем памяти можно уменьшить, если упаковать матрицу в массивы смежности. Для рассматриваемого примера такие массивы представлены на рис.2.24.

Таблица 2.7.
Матрица смежности дерева, изображенного на рис.2.23
0	0	1	0	1	0	0
0	0	0	0	0	1	0
0	0	0	0	0	0	0
0	0	0	0	0	0	0
0	1	0	1	0	0	1
0	0	0	0	0	0	0
0	0	0	0	0	0	0

	1	2	3	4	5	6	7	8
S	3	5	6	2	4	7
U	1	3	4	4	4	7	7	7
Рис.2.24. Упаковка матрицы смежности (табл. 2.7) в массивы смежности

Есть еще один более существенный недостаток. Этот недостаток заключается в трудности восстановления путей, ведущих в вершины дерева из его корня (из вершины, в которую нет входящих дуг). Действительно, в рассматриваемом примере при восстановлении пути из вершины 1 (корень) в вершину 6 (путь 1,5,2,6) возникает неоднозначность - куда двигаться из вершины 1 в 3 или 5 вершину. Аналогично из 5 вершины не ясно, куда двигаться в 2,4 или 7 вершины. Такие неоднозначности приводят к итерационному алгоритму восстановления путей, что является существенным недостатком.

Наиболее выгодно ориентированное дерево, состоящее из n вершин, пронумерованных числами 1,2,...n, сохранить в массиве P из n ячеек, также пронумерованных числами 1,2,...n. Элементы массива P формируются следующим образом: P_i=номер вершины, предшествующей вершине i, если такая вершина есть, и P_i=0 в противном случае (вместо нуля можно использовать любое число, не использующееся для нумерации вершин дерева). Для дерева, представленного на рис. 2.23, такой массив представлен на рис.2.25.

	1	2	3	4	5	6	7
P	0	5	1	5	1	2	5
Рис.2.25. Массив для хранения дерева, изображенного на рис.2.23

Если дерево хранится в таком массиве, то путь w из корня k в некоторую вершину v легко восстановить с конца, т.е. в обратном порядке от вершины v к вершине k:

w=v, P[v], P[P[v]], P[P[P[v]]],...,k.

При восстановлении пути из вершины 1 в вершину 6 для рассматриваемого дерева получим следующую последовательность действий: v=6, P[6]=2, P[2]=5, P[5]=k=1. Итак, w=6,2,5,1. Перевернув последовательность w, получим искомый путь 1,5,2,6. Восстановление пути удобно осуществлять с помощью стека. Разработайте алгоритм восстановления пути самостоятельно.