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

Список смежности для вершины v — это для орграфа список концов дуг, исходящих из вершины v, а для неориентированно графа — список смежных с v вершин. Для орграфа G1 и графа G2 списки смежности выглядят так:
G1                  G2
1 => 2→3             1=> 2→4
2=> NULL            2=> 1→3→4
3=> 2→4→5        3=> 2-→4
4=>5                     4=>1→2→3→5→6
5=>6                     5=>4→6
6 =>4                    6=>4→5
Здесь: => — указатель начала списка, → связь вершин в списке смежности.

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

Проще использовать для представления списков смежности графа двухмерный массив или два одномерных массива. Рассмотрим вариант представления неориентированного графа в виде списков смежности на примере простого графа.

Рис. Представление графа в виде списков смежности

Граф имеет Р=5 нумерованных вершин (1,2...5) и Q=6 рёбер. Зададим граф в виде ребер, указывая (U,V), где u и v — номера вершин, 1=(u,v)≤P: (1,2); (1,3); (2,3); (2,4); (3,5); (5,4). Эти данные являются исходными при представлении графа в виде списков смежности для вершин 1,2,...Р. Списки смежности представим в векторной памяти в виде двух одномерных массивов с индекса 1,2,...N, где N=P+2Q. В массиве NEXT первые Р элементов содержат указатели списков (индексы строк массивов) для каждой из вершин графа 1,2,...Р. Остальные 2Q элементы массива NEXT содержат указатели на следующие элементы в каждом из списков. Первые Р элементов массива ADJ не используются, в остальных 2Q элементах содержатся номера вершин ребер (v,u) в пордке их поступления при формировании массива. Обратите внимание на то, что ребро задается вершинами (u,v), а в массив верп ны заносятся как (v,u).
Алгоритм построения и формирования массивов ADJ и NEXT достаточно прост.

1. Ввод числа вершин Р и числа ребер Q, Q≤P(P - 1).
2. Определение размера массивов N=P+2Q, получение динамической памяти для них (ADJ и NEXT), если они не были определены в программе как переменные.
3. Обнуление первых Р элементов массивов ADJ и NEXT.
4. В цикле для каждого ребра вводятся номера его вершин (U,V), которые размеща-ются в последовательных ячейках ADJ, начиная с элемента ADJ[P+1] в порядке (V,U), формируются связи (указатели) списков.