Диссертация (792664), страница 9
Текст из файла (страница 9)
В случаевыполнения этого условия происходит переход к блоку 9, в ином случае – к блоку12.В блоках 9 – 11 организован цикл по всем желтым вершинам, соседним стекущей серой вершиной.В блоке 9 – начинается цикл по желтым вершинам, соседним с текущейсерой вершиной.68110.1.Продолжение построениядерева(следующая итерация)Начало2.НетТекущая вершина белая?Да3.4.Создаем исток дереваДобавление в дерево вершины,соответствующей текущейвершине графа, как смежной кзапомненной вершине дерева5.Сохранение информации обокраске текущей вершины6.Раскрашивание текущейвершины графа в серый цвет7.Цикл по всем серым вершинамграфа8.С серымвершинам соседствуютжелтые вершины?НетДа9.Цикл по желтым вершинам,соседним с текущей серой12.1Раскрашивание серой вершиныграфа в черный цвет11.Цикл по желтым вершинам,соседним с текущей серой13.Цикл по всем серымвершинам графа14.Восстановление цвета текущейвершины10.15.КонецПродолжение построениядерева (предыдущаяитерация)1Рисунок 3.8 – Схема алгоритма построения дерева69В блоке 10 – происходит переход к следующему шагу построения дерева(блок 1).
В качестве новой текущей вершины рассматривается текущая желтаявершина, в качестве запомненной вершины – текущая серая. Блок разбит на двечасти с целью обозначения дальнейшего пути выполнения действий в процессевозврата из рекурсивно вызванных процедур (переход от блока 15).В блоке 11 – завершается цикл по всем желтым вершинам, соседним стекущей серой вершиной.В блоке 12 – происходит раскрашивание серой вершин графа в черный цвет.В блоке 13 – завершается цикл по всем серым вершинам графа.В блоке 14 – происходит восстановление раскраски текущей вершины послевозврата из рекурсивных процедур после достижения граничного условияпостроения дерева.Блоком 15 – отмечено завершение алгоритма.На Рисунке 3.9 представлены деревья, полученные на основе информации,визуализированной на Рисунке 3.7, в результате исполнения разработанногоалгоритма.
В названиях вершин построенного дерева последние две цифрысовпадают с цифрами в названии соответствующей вершины в исходном графе.Цифры,расположенныелевее,даютинформациюотом,вкакойпоследовательности добавлялись вершины в дерево, они соответствуют числувершин в дереве к моменту добавления рассматриваемой вершины. Деревья,полученные для трех-, четырех- и шестистрелочной станций содержат большоеколичество вершин, поэтому они представлены в сильно уменьшенном виде, атакже представлены их фрагменты.Рисунок 3.9.а – Дерево, полученное на основе информации для двухстрелочной станции70Рисунок 3.9.б – Дерево, полученное на основе информации для трехстрелочной станции7172Рисунок 3.9.в – Фрагмент дерева, полученного для трехстрелочнойстанцииРисунок 3.9.г – Дерево, полученное на основе информации для четырехстрелочной станции7374Рисунок 3.9.д – Фрагмент дерева, полученного для четырехстрелочнойстанцииРисунок 3.9.е – Дерево, полученное на основе информации для шестистрелочной станции7576Рисунок 3.9.ж – Фрагмент дерева, полученного для четырехстрелочнойстанции3.4.3Уплотнение графаНа Рисунке 3.10 представлен алгоритм уплотнения графа.Припервомвызовеалгоритмавкачестветекущейвершинырассматривается белая вершина графа, а запомненной вершины не существует.Блоком 1 – отмечено начало алгоритма.В блоке 2 – проверяется условие наличия в «уплотненном» графевершины, соответствующей текущей.
В случае, если она не существует,происходит переход к блоку 3, в ином случае – переход к блоку 4.В блоке 3 – происходит создание в «уплотненном» графе вершины,соответствующей текущей.В блоке 4 – проверяется условие наличия в «уплотненном» графе ребра,направленного от запомненной ранее вершины к вершине, соответствующейтекущей. В случае, если оно не существует, происходит переход к блоку 5, вином случае – переход к блоку 6.В блоке 5 – создается в «уплотненном» графе ребро, направленное отзапомненной ранее вершины к вершине, соответствующей текущей.7711.11.Продолжение построения«уплотненного» графа(следующая итерация)Начало2.3.4.5.В «уплотненномграфе» Существуетвершина, соответствующаятекущей?ДаНетСоздание в «уплотненном»графе вершины,соответствующей текущейВ «уплотненном» графесуществует ребро,направленное от запомненнойранее вершины к вершине,соответствующей текущей?ДаНетСоздание в «уплотненном»графе ребра, направленного отзапомненной ранее к текущей6.Сохранение информации обокраске текущей вершины7.Раскрашивание текущейвершины графа в серый цвет8.Цикл по всем серым вершинамграфа9.С серойвершиной соседствуютжелтые вершины?НетДа10.Цикл по желтым вершинам,соседним с текущей серой13.Раскрашивание серой вершиныграфа в черный цвет112.Цикл по желтым вершинам,соседним с текущей серой14.Цикл по всем серым вершинамграфа15.Восстановление цвета текущейвершины11.16.КонецПродолжение построения«уплотненного» графа(следующая итерация)1Рисунке 3.10 – Схема алгоритма уплотнения графа78В блоке 6 – фиксируются параметры текущей итерации процесса с цельюкорректного их восстановления после возврата из рекурсивных процедур последостижения граничного условия построения «уплотненного» графа: сохранениеинформации об раскраске текущей вершины.В блоке 7 – раскрашивается текущая вершина в серый цвет.В блоках 8 – 15 организован цикл по всем серым вершинам графа.В блоке 8 – начинается цикл по всем серым вершинам графа.В блоке 9 – проверяется условие наличия в графе смежных серойвершине желтых вершин.
Если такие вершины существуют, то происходитпереход к блоку 10, в ином случае – переход к блоку 14.В блоках 10 – 13 организован цикл по всем желтым вершинам, соседнимс текущей серой вершиной.В блоке 10 – начинается цикл по желтым вершинам, смежным текущейсерой вершине.В блоке 11 – происходит переход к следующему шагу построения«уплотненного» графа (блок 1).
В качестве новой текущей вершинырассматривается текущая желтая вершина, в качестве запомненной вершины –текущая серая. Блок разбит на две части с целью обозначения дальнейшегопути выполнения действий в процессе возврата из рекурсивно вызванныхпроцедур (переход от блока 16).В блоке 12 – завершается цикл по всем желтым вершинам, соседним стекущей серой вершиной.В блоке 13 –раскрашиваются серые вершины графа в черный цвет.В блоке 14 – завершается цикл по всем серым вершинам графа.В блоке 15 – восстанавливается раскраска текущей вершины послевозврата из рекурсивных процедур после достижения граничного условияпостроения «уплотненного» графа.Блоком 16 – отмечено завершение алгоритма.79На Рисунке 3.11 представлены «уплотненные» графы, полученные наоснове информации, визуализированной на Рисунке 3.7, в результате исполненияразработанногоалгоритма.На«уплотненных»графахкраснымцветомобозначены ребра, входящие в пути, соответствующие последовательностизаполнения указателей ночной расстановки на фрагментах ПГД, представленныхна Рисунке 3.3.Рисунок 3.11.a – «Уплотненный» граф, полученный для двухстрелочнойстанции80Рисунок 3.11.б – «Уплотненный» граф, полученный на основе информациидля трехстрелочной станцииРисунок 3.11.в – «Уплотненный» граф, полученный на основе информациидля четырехстрелочной станции81Рисунок 3.11.г – «Уплотненный» граф, полученный на основе информациидля шестистрелочной станции3.4.4Алгоритм разворачивания «уплотненного» графа в деревоНа Рисунке 3.12 представлен алгоритм разворачивания «уплотненного»графа в дерево.Как было показано в Таблице 2.1, при сжатом представлении информации опоследовательности заполнения и освобождения указателей ночной расстановкисоставов в виде уплотненных графов требуется её дополнительная обработка прииспользовании в сценариях построения ПГД.Блоком 1 – отмечено начало алгоритма.В блоке 2 –добавляется текущая вершина в путь.В блоке 3 –сохраняется информация о цвете текущей вершины.В блоке 4 –раскрашивается текущая вершина графа в серый цвет.В блоках 5 – 12 организован цикл по всем серым вершинам графа.8219.1.Продолжение построенияпути(следующая итерация)Начало2.Добавление текущей вершиныв путь3.Сохранение информации оцвете текущей вершины4.Раскрашивание текущейвершины графа в серый цвет5.Цикл по всем серым вершинамграфа6.НетС серымвершинам соседствуютжелтые вершины?7.Цикл по желтым вершинам,соседним с текущейДа серой8.Вершина несмежная с другими вершинами, невключенными в путь, или существуетребро, направленное к ним израссматриваемойДа11.Раскрашивание серой вершиныграфа в черный цветНет110.Цикл по желтым вершинам,соседним с текущей серой12.Цикл по всем серым вершинамграфа13.Восстановление цвета текущейвершины9.14.КонецПродолжение построенияпути(следующая итерация)1Рисунок 3.12 – Алгоритм разворачивания «уплотненного» графа в дерево83В блоке 5 – начинается цикл по всем серым вершинам графа.В блоке 6 – проверяется условие наличия желтой вершины, соседней стекущей.
В случае, если они существуют, происходит переход к блоку 7, в иномслучае – переход к блоку 10.В блоках 7 – 10 организован цикл по желтым вершинам, соседним стекущей серой.В блоке 7 – начинается цикл по желтым вершинам, соседним с текущейсерой.В блоке 8 – проверяется следующее условие: вершина не является смежнойс другими вершинами, не включенными в путь, или существует ребро,направленное к ним из рассматриваемой.В блоке 9 – происходит переход к следующему шагу построения пути (блок1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
