На этом шаге мы рассмотрим представление графа с помощью списков смежности.
Представление графа с помощью матрицы смежностей зачастую неудобно, поскольку количество вершин требуется знать заранее. Если граф должен создаваться или изменяться во время исполнения программы, то для каждого добавления или удаления вершины надо строить новую матрицу. Кроме того, даже если граф содержит малое число ребер (дуг) и матрица смежностей состоит в основном из нулей, память должна быть отведена для всех возможных дуг вне зависимости от того, существуют ли они. Если граф содержит n вершин, то должна быть отведена память для n2 элементов.
Как и следовало ожидать, возможное решение - для представления графа использовать динамическую (связанную) структуру.
Укажем вначале на примере самый очевидный (в силу чего громоздкий и практически никогда не применяемый) способ представления графов с помощью динамических структур.
Например, если ориентированный граф имеет следующий вид:
Рис.1. Пример графа
то без всяких ухищрений представим его в памяти следующим образом (символ N обозначает NULL):
Рис.2. Представление графа
Совершенно ясно, что посредством ссылок можно выразить все связи в структуре, моделирующей ориентированный граф: вершинам графа соответствуют сами динамические переменные, а ребрам - ссылки.
Однако, так как в графе может существовать дуга между любыми двумя вершинами, то необходимо заранее знать, какое количество указателей резервировать для динамической переменной, а после построения может оказаться, что в структуре содержится очень много нулевых указателей (содержащих NULL).
Поэтому мы пойдем другим путем, и первым нашим шагом будет изучение классической структуры, называемой списками смежности.
Список смежности содержит для каждой вершины v, принадлежащей V, список смежных ей вершин. Используя терминологию языка C++, можно утверждать, что каждый элемент такого списка является записью R, содержащей в поле (*R).Key вершину графа, а в поле (*R).Sled - указатель на следующую запись в списке; ясно, что для последней записи в списке (*R).Sled содержит NULL.
Обозначим beg[v] - указатель на начало списка, содержащего вершины, смежные с вершиной v.
Изобразим схематически представление неориентированного графа с помощью списков смежности (символ N обозначает NULL):
Рис.3. Представление неориентированного графа
Отметим, что для неориентированных графов каждое ребро представлено в списках смежности дважды.
Число ячеек памяти, необходимое для представления графа с помощью списков смежности, будет, очевидно, иметь порядок |V|+|E|.
На следующем шаге мы рассмотрим простейшие операции над графами, представленными списками смежности.
