Студопедия — While не конец файла do
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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






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

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

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

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

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

го графа)

end;

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

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

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

СП(v1): v3 v4

СП(v3): v1 v4

СП(v4): v1 v3 v5

СП(v5): v4;

б) для графа (рис.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. Добавление ребра (дуги) (vi, vj) в граф G.

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

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

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

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

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

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

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

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








Дата добавления: 2014-11-10; просмотров: 480. Нарушение авторских прав; Мы поможем в написании вашей работы!



Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

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

Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

Ваготомия. Дренирующие операции Ваготомия – денервация зон желудка, секретирующих соляную кислоту, путем пересечения блуждающих нервов или их ветвей...

Билиодигестивные анастомозы Показания для наложения билиодигестивных анастомозов: 1. нарушения проходимости терминального отдела холедоха при доброкачественной патологии (стенозы и стриктуры холедоха) 2. опухоли большого дуоденального сосочка...

Сосудистый шов (ручной Карреля, механический шов). Операции при ранениях крупных сосудов 1912 г., Каррель – впервые предложил методику сосудистого шва. Сосудистый шов применяется для восстановления магистрального кровотока при лечении...

Способы тактических действий при проведении специальных операций Специальные операции проводятся с применением следующих основных тактических способов действий: охрана...

Искусство подбора персонала. Как оценить человека за час Искусство подбора персонала. Как оценить человека за час...

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

Studopedia.info - Студопедия - 2014-2024 год . (0.011 сек.) русская версия | украинская версия