Списки смежности

Данный способ представления графов в значительной степени лишен избыточности, присущей табличным представлениям.

Пусть G = (V, U) - некоторый граф, для которого

V = { v ₁,..., v _n} и U = { u ₁,..., u _k}.

Образуем два массива, которые обозначим как A и B.

Массив A состоит из n элементов, по одному для каждой вершины графа, а B - столько элементов, сколько существует концов различных ребер в G.

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

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

Здесь список L (e) является пустым.

Элементы списков L (v ₁)- L (v _n) последовательно записываются в массив B.

В первый, второй и последующие элементы массива A помещаются значения номеров элементов в B, которые являются в массиве B началами списков L (v ₁), L (v ₂) и т.д.

Если при этом некоторый список L (v_i) оказывается пустым, значение ссылки в элементе A (i) полагается равным 0. Такое представление графов является полным, поскольку в нем элементами массива A представлены все вершины, а массив B представляет все ребра графа. Множество ребер, выходящих из произвольной вершины v_i представлено своими концами в части массива B, начинающейся с элемента A (i) и заканчивающейся либо в элементе A (j) – 1, где j = min t (t > i & A (t) ¹ 0), либо в последнем элементе массива B.

Для рассматриваемого графа массивы A и B имеют вид:

A 1 4 5 6 0 9