Списки смежности
Данный способ представления графов в значительной степени лишен избыточности, присущей табличным представлениям.
Пусть G = (V, U) - некоторый граф, для которого
V = { v 1,..., v n} и U = { u 1,..., u k}.
Образуем два массива, которые обозначим как A и B.
Массив A состоит из n элементов, по одному для каждой вершины графа, а B - столько элементов, сколько существует концов различных ребер в G.
При построении списков смежности для каждой вершины графа сформируем список вершин, в которые ведут ребра, выходящие из выбранной вершины. То есть элементы списков содержат концы всех ребер, выходящих из соответствующих вершин.
Для графа, изображенного на рис. 5.3., такие списки имеют вид:
Вершина
| Список
| a
b
c
d
e
f
| L(a) = f c b
L(b) = d
L(c) = e
L(d) = d b f
L(e) =
L(f) = d
| Здесь список L (e) является пустым.
Элементы списков L (v 1)- L (v n) последовательно записываются в массив B.
В первый, второй и последующие элементы массива A помещаются значения номеров элементов в B, которые являются в массиве B началами списков L (v 1), L (v 2) и т.д.
Если при этом некоторый список L (vi) оказывается пустым, значение ссылки в элементе A (i) полагается равным 0. Такое представление графов является полным, поскольку в нем элементами массива A представлены все вершины, а массив B представляет все ребра графа. Множество ребер, выходящих из произвольной вершины vi представлено своими концами в части массива B, начинающейся с элемента A (i) и заканчивающейся либо в элементе A (j) – 1, где j = min t (t > i & A (t) ¹ 0), либо в последнем элементе массива B.
Для рассматриваемого графа массивы A и B имеют вид:
A 1 4 5 6 0 9
Дата добавления: 2015-09-27 | Просмотры: 632 | Нарушение авторских прав
|