Главная Промышленная автоматика.

ностей удобно для тех алгоритмов на графах, которым часто нужно знать, есть ли в графе данное ребро, ибо время, необходимое для определения наличия ребра, фиксировано и не зависит от V и ЦЦ. Основной недостаток применения матрицы смежностей заключается в том, что она занимает память объема V* даже тогда, когда граф содержит только 0(У) ребер. Уже начальное заполнение матрицы смежностей посредством "естественной" процедуры требует времени 0(V1*), что сводит на нет алгоритмы сложности 0(1111) при работе с графами, содержащими лишь 0(У) ребер. Хотя разработаны методы для преодоления этой трудности (см. упр. 2.12), почти неизбежно возникают другие проблемы, которые приводят к тому, что алгоритмы сложности 0(У), основанные на работе с матрицей смежностей, встречаются редко.

Интересной альтернативой является представление строк и (или) столбцов матрицы смежностей в виде двоичных векторов. Такое


1 2 3 4

Узе/г 1

Пустой стсок

Узеуг

Шпи<

2 3 4 5 6 7 8 9

КОНЕЦ СЛЕДУЮЩИЙ

Рис. 2.6. Ориентированный граф и его представления: а - ориентированный граф; б - матрица смежностей; в - списки смежностей; г - табличное представление

списков смежностей.

3 А. Ахо, Дж. Хопкрофт, Дж. Ульман

«5



представление может способствовать значительной эффективности алгоритмов на графах.

Еще одно возможное представление графа - с помощью списков. Списком смежностей для узла v называется список всех узлов W, смежных с v. Граф можно представить с помощью списков смежностей, по одному для каждого узла.

Пример 2.2. На рис. 2.6,а изображен ориентированный граф, содержащий четыре узла, а на рис. 2.6,6 - его матрица смежностей. На рис. 2.6,в показаны четыре списка смежностей, по одному для каждого узла. Например, из узла 1 в узлы 2 и 4 идут ребра, так что список смежностей для 1 содержит компоненты 2 и 4, связанные в смысле рис. 2.1.

Табличное представление списков смежностей приведено на рис. 2.6,2. Каждая из первых четырех ячеек в массиве СЛЕДУЮЩИЙ содержит указатель на первый узел списка смежностей, а именно СЛЕДУЮЩИЙ[1] указывает на первый узел списка смежностей для узла i. Заметим, что СЛЕДУЮЩИИ[3]=0, поскольку в списке смежностей для узла 3 нет узлов. Остальные составляющие массива СЛЕДУЮЩИЙ представляют ребра графа. Массив КОНЕЦ содержит узлы из списков смежностей. Таким образом, список смежностей узла 1 начинается в ячейке 5, ибо СЛЕДУЮ-ЩИЙ[1]=5, КОНЕЦ[5]=2; это показывает, что есть ребро (1, 2). Равенства СЛЕДУЮЩИЙ[5]=6 и КОНЕЦ[6]=4 означают, что есть ребро (1, 4), а СЛЕДУЮЩИЙ[6]=0 - что больше нет ребер, начинающихся в 1. □

Заметим, что представление графа в виде списков смежностей требует памяти порядка УУЩ-ЦН. Представлением с помощью списков смежностей часто пользуются, когда £<У?.

Если граф неориентирован, то каждое ребро {v, w) представляется дважды: один раз в списке смежностей для v и один раз в списке смежностей для w. В этом случае можно добавить новый массив, называемый СВЯЗЬ, чтобы коррелировать оба экземпляра неориентированного ребра. Таким образом, если i - ячейка, соответствующая узлу W в списке смежностей для v, то СВЯЗЬ[/] - ячейка, соответствующая узлу v в списке смежностей для w.

Если мы хотим с удобством удалять ребра из неориентированного графа, то списки смежностей можно связать дважды (как описано в разд. 2.1). Это обычно бывает нужно потому, что даже если удалять всегда ребро (v, w), стоящее первым в списке смежностей узла V, все равно может оказаться, что ребро, идущее в обратном направлении, стоит в середине списка смежностей узла w. Чтобы быстро удалить ребро (v, w) из списка смежностей для w, надо уметь быстро находить ячейку, содержащую предыдущее ребро в этом списке смежностей.



2.4. ДЕРЕВЬЯ

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

Определение. Ориентированный граф без циклов называется ориентированным ациклическим графом. (Ориентированное) дерево (иногда его называют корневым деревом) - это ориентированный ациклический граф, удовлетворяющий следующим условиям:

1) имеется в точности один узел, называемый корнем, в который не входит ни одно ребро,

2) в каждый узел, кроме корня, входит ровно одно ребро,

3) из корня к каждому узлу идет путь (который, как легко показать, единствен).

Ориентированный граф, состоящий из нескольких деревьев, называется лесом. Леса и деревья - столь часто встречающиеся частные случаи ориентированных ациклических графов, что для описания их свойств стоит ввести специальную терминологию.

Определение. Пусть F=(V, Е) - граф, являющийся лесом. Если {v, w) принадлежит Е, то v называется отцом узла w, aw - сыном узла V. Если есть путь из у в ш, то у называется предком узла w, а w- потомком узла v. Более того, если ьфгш, то v называется подлинным предком узла w,aw - подлинным потомком узла у. Узел без подлинных потомков называется листом. Узел v и его потомки вместе образуют поддерево леса F, и узел v называется корнем этого поддерева.

ЛЕВЫЙСЫН ЛРАВЫЙСЫН


2 3 4 5 6 f 8 9

Рис. 2.7. Двоичное дерево и его представление.





0 1 2 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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0039