На этом шаге мы рассмотрим создание и использование списков инцидентности.
- Определение.
- Списками инцидентности (в программировании) называется способ представления графа в виде массива линейных списков, каждый элемент которого соответствует вершине графа v ∈ V и представляет собой список смежных ей вершин.
Пример (представления неориентированного графа). Указатель Beg[v] является указателем на начало списка, содержащего вершины из множества вершин, смежных с данной вершиной v.
Для неориентированных графов каждое ребро представлено в списках инцидентности дважды.
Рис.1. Граф и соответствующий ему массив указателей
Число ячеек памяти, необходимое для представления графа с помощью списков инцидентности, имеет порядок M+N.
Замечание (важное). Во многих алгоритмах структура графа динамически модифицируется добавлением и удалением рёбер. В таких случаях полагаем, что в наших списках инцидентности элемент списка Beg[u], содержащий вершину v, снабжен указателем на элемент списка Beg[v], содержащий вершину u, и что каждый элемент списка содержит указатель не только к следующему элементу, но и к предыдущему. Тогда, удаляя некоторый элемент из списка, мы можем легко за число шагов, ограниченное константой, удалить другой элемент, представляющий то же самое ребро, не просматривая список, содержащий этот элемент.
На следующем шаге мы рассмотрим список ребер (дуг).
