While не конец файла do

begin ввод и проверка nv;

ввод и проверка kv;

инкремент счётчика рёбер (дуг);

добавить запись kv в список nv;

добавить запись nv в список kv; (для неориентированно-

го графа)

end;

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

Вывод списков инцидентности графа на экран или в файл осуществляется в соответствии со структурой аналогичной файлу «таблица смежности». При этом просматривается список каждой вершины, если он непуст, то выводится: СП, затем в скобках вершина,:, список вершин смежных с ней. Например, выводимая информация имеет вид:

а) для графа (рис.2)

СП(v₁): v₃ v₄

СП(v₃): v₁ v₄

СП(v₄): v₁ v₃ v₅

СП(v₅): v₄;

б) для графа (рис.4)

Списки следования: Списки предшествования:

СП [1]: 2 3 СП [1]: 3

СП [2]: 3 СП [2]: 1

СП [3]: 1 СП [3]: 2 1.

Для вывода списка инцидентности или любого другого вида его обработки необходимо просмотреть этот список. Просмотр списка выполняется с помощью итераторов, которые являются аналогами указателей для контейнерных классов. Для этого итератору текущего элемента списка присваивается значение начала списка, а также запоминается итератор конца списка. Пока не достигнут конец списка, выполняются действия по обработке элемента списка и увеличение итератора текущего элемента списка. Обращение к элементу, адресуемому итератором, выполняется также, как и для указателей, операторами * или ->.

Например, фрагмент программы просмотра i -го списка графа имеет вид:

list < int>:: iterator pl = graf [ i ].begin(), el = graf [ i ].end();

while (pl! = el) блок обработки элемента;

При работе с графом часто требуется выполнить действия, изменяющие его структуру. К ним относятся:

1. Добавление ребра (дуги) (v_i, v_j) в граф G.

Для этого нужно:

а) добавить запись с вершиной v_j в список инцидентности вершины v_i;

б) для неориентированного графа добавить запись с вершиной v_i в список инцидентности вершины v_j.

2. Удаление ребра (дуги) (v_i, v_j) из графа G (осуществляется аналогично добавлению ребра (дуги)).

3. Удаление вершины v_i из графа G.

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

Часто кроме изменения структуры графа для более эффективной работы алгоритмов требуется сортировка (упорядочение) списков инцидентности.

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