Некоторые СД для хранения графов и деревьев

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

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

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

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

Таблица 6.2

Матрица смежности графа, изображенного на рис.6.10

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

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

Таблица 6.3.

Матрица инцидентности графа, изображенного на рис.6.10

				-1
-1
	-1
		-1	-1

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

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

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

Таблица 6.4

Матрица весов графа, изображенного на рис.6.11

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

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

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

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

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

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

Еще один способ хранения графов - это массив рёбер, то есть массив записей, в котором перечислены все рёбра графа (каждая запись кодирует ребро). Массив рёбер графа, представленного на рис. 6.11, приведен на рис. 6.13. Здесь массив занимает 48 ячеек.

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

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

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

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

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

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

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

Например, дерево, изображенное на рис.6.16 может быть сохранено матрицей смежности, представленной в табл.6.5.

Таблица 6.5

Матрица смежности дерева, изображенного на рис.6.16

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

	1	2	3	4	5	6	7	8
S
U

Рис.6.17. Упаковка матрицы смежности (табл. 6.4) в массивы смежности

Есть еще один более существенный недостаток. Этот недостаток заключается в трудности восстановления путей ведущих в вершины дерева из его корня (из вершины, в которую нет входящих дуг). Действительно, в рассматриваемом примере при восстановлении пути из вершины 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 в противном случае[3]. Для дерева представленного на рис. 6.16 такой массив представлен на рис.6.18.

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

Если дерево хранится в таком массиве, то путь 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.

Восстановление пути удобно осуществлять с помощью стека. Выполните реализацию восстановления пути с помощью стека самостоятельно.

Вопросы для повторения

1. Понятие абстрактного типа данных.

2. Понятие O-символики.

3. АТД список, операторы списка.

4. Реализация списков посредством массивов.

5. Реализация списков с помощью указателей.

6. Реализация списков с помощью курсоров.

7. АТД стек, операторы стека.

8. Реализация стеков.

9. АТД очередь, операторы очереди.

10. Реализация очередей.

11. Понятие графа (неориентированного графа).

12. Понятие вершины графа.

13. Понятие ребра графа.

14. Понятие ориентированного графа.

15. Понятие дуги орграфа.

16. Понятие смежности.

17. Понятие концевой вершины.

18. Понятие инцидентности.

19. Понятие петли.

20. Понятие кратных ребер.

21. Понятие параллельных дуг.

22. Понятие цепи.

23. Понятие пути.

24. Понятие маршрута.

25. Понятие цикла.

26. Понятие контура.

27. Понятие связного графа.

28. Понятие ациклического графа.

29. Понятие дерева.

30. Понятие леса.

31. Понятие подграфа.

32. Понятие покрывающего (или остовного) дерева.

33. Понятие матрицы смежности.

34. Понятие матрицы инцидентности.

35. Хранение взвешенных графов с помощью матриц весов.

36. Упаковка матриц.

37. Хранение графов с помощью массивов ребер.

38. Хранение графов с помощью списков смежности.

39. Хранение графов с помощью списков ребер.

40. Хранение деревьев.

Резюме по теме

В данной теме рассмотрены различные методы организации данных в памяти ЭВМ.