XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 51
Текст из файла (страница 51)
Просмотрим неотмеченные вершины из ее списка смежности и отметим вершины ее и пт, присваивая им номера 7 и 8 соответственно. Теперь, когда список смежности вершины ез обработан полностью, перейдем в вершину ее. Так как в ее списке смежности нет неотмеченных вершин, перейдем в вершину в7. Здесь также в списке смежности нет неотмеченных вершин. Все вершины обработаны, и поиск в ширину для графа закончен.
Результаты поиска в ширину из вершины ез в ориентированном графе представлены на рис. 5.21, б. Обратим внимание на то, что нумерация вершин при поиске в ширину отличается от нумерации вершин при поиске в глубину. Так, в ориентированном графе на рис. 5.21, б мы сразу отмечаем оба элемента списка смежности вершины ее. Поэтому вершине, получившей при поиске в глубину номер 4, при поиске в ширину присваивается номер 3. Перейдем теперь к подробному описанию алгоритмов поиска в глубину и поиска в ширину.
Рассмотрим алгоритм поиска в глубину в неориентированном графе. Будем считать, что граф задан списками смежности, собранными в массив лидеров. При поиске вершины графа нумеруются в порядке их посещения. Номер вершины е графа, присваиваемый ей при поиске в глубину, обозначим В[в] и будем называть ХЭ-номером. 5.5. Методы обхода вершин 317 В процессе обхода будем находить 4ундаментпеьаьные цаеалы графа. Понятие фундаментального цикла в неориентированном графе вводится следующим образом. Пусть в не- ориентированном графе 0 = (У, Е) произвольно фиксирован максимааьныб остповныб лес (см.
теорему 5.3). Для связного графа зто будет максимальное остовное дерево. Множество его ребер обозначим Т. Все ребра из Т назовем древесньами, а ребра исходного графа С, не принадлежащие Т, — обратимыми. Таким образом, фиксируя в графе С максимальный остовный лес, мы тем самым фиксируем разбиение множества его ребер на подмножества древесных и обратных ребер. В силу максимальности остовного леса любая пара вершин графа С, принадлежащвх одной и той же компоненте связности, соединена цепью, все ребра которой являются древесными. Возьмем теперь произвольно две вершины и и е, принадлежащие одной и той же компоненте связности графа С.
Пусть зти вершины соединены обратным ребром. Поскольку они также соединены цепью, содержащей исключительно древесные ребра, то существует цикл, содержащий зти две вершины, в котором будет единственное обратное ребро (п,е). Любой цикл графа С, содержащий только одно обратное ребро, назовем фундаментальным. Докажем, что не существует двух различных фундаментальных циклов, содержащих одно и то же обратное ребро (рис. 5.22).
Действительно, если предположить противное,то С возникает цикл С, содержащий лишь древес- Рис. 6.22 ные ребра, что невозможно. Итак, фиксируя в графе максимальный остовный лес, мы тем самым фиксируем взаимно однозначное соответствие между множеством обратных ребер и множеством фундаментальных циклов. Одним из способов построения максимального остовного леса может служить поиск в глубину. Именно при поиске в глубину всякое ребро, по которому из текущей вершины мы 318 5.
'ГЕОРИЯ ГРАФОВ попадаем в неотмеченную ранее вершину, будет древесным. Каждое ребро, не являющееся древесным, будет обратным. Максимальный остовный лес, находвмый с помощью алгоритма поиска в глубину, называют остпоеным лесом поиска е влубинуили злубинным остпоеным лесом.
Заметим, что классификация ребер зависит от хода работы алгоритма, который определяется стартовой вершиной и расположением вершин в списках смежности. Таким образом, алгоритм поиска в глубину в неориентированном графе может быть использован для вычисления множества фундаментальных циклов графа, т.е. решения одной из задач глобального анализа.
Отметим, что не всякий максимальный остовный лес может быть получен с помощью алгоритма поиска в глубину. Например, для графа, юображенного на рис. 5.23, выделенный максимальный остовный лес нельзя получить при поиске в глубину, из Рне. 6.23 какои бы вершины мы не начинали поиск. Для организации работы алгоритма поиска в глубину используется способ хранения данных, называемый ставкам. Элементы в стеке упорядочиваются в порядке поступления.
В стек можно добавлять новые элементы и из него можно извлекать элементы. При этом доступен только последний добавленный элемент — вершина стпека, чем и определяется режим работы стека (последним пришел — первым ушел). Образно стек можно представить в виде стопки тарелок. Из стопки можно взять только верхнюю тарелку и только наверх можно добавить новую. Обычно стек реализуется в виде списка. В алгоритме поиска в глубину используетсл стек вершин.
Мы будем считать, что из стека можно считывать информацию без юменения его содержимого, но в том порядке, в каком ее удаляли бы из стека. Указанная операция считывания понадобится нам для поиска фундаментальных циклов. 6.5. Методы обхода верввое Алгоритм поиска в глубину 318 Вход. 1раф С = ( т', Е), заданный списками смежности. Выход. Множества 21ве древесных и Вася обратных ребер соответственно; множество Ре фундаментальных циклов, массив Р, содержащий Р-номера вершин. О. Просмотреть массив лидеров и сформировать множество ре вершин графа. Это множество используется для хранения новых (не обработанных алгоритмом) вершин.
В ходе работы алгоритма обработанные вершины будут удаляться нз этого множества. В процессе работы алгоритма для каждой вершины е необходимо знать, какие вершины из ее списка смежности Це] обработаны на предыдущих шагах работы алгоритма. Для этого формируется массив Ь„размера Щ, в котором хранятся номера первых еще не обработанных алгоритмом вершин списка смежности Ь[е] каждой вершины е.
Первоначально все элементы массива Ьр полагают равными 1. Стек вершин ВТАСК и список вершин фундаментального цикла Срс1е положить пустыми (БТАСК = Я, Срс1е = И). Множества Лес древесных ребер, Вася обратных ребер и Ео фундаментальных циклов положить пустыми (Бее = И, Вася = И, Ре = И). Массив Р-номеров Р обнулить.
Задать начальную вершину для поиска (е = ев). (Обычно это первая вершина массива лидеров.) Счетчик Р-номеров вершин сомни положить равным 1 (соип$ = 1). 1. Если множество то не пусто (~~ ф Я), перейти на шаг 2, если иначе — на шаг 8 (выход). 2. Если стек пуст (ЯТАСК = Я) и алгоритм стартует из вершины ео (сопим = 1), то перейти на шаг 3, если иначе, то выбрать нз множества ~~ произвольную вершину, из которой поиск в глубину будет продолжен (е = и, и Е К>), и перейти на шаг 3. 3. Поместить текущую вершину е в стек ЯТАСК. Присвоить вершине е Р-номер (Р[е] = соип$). Увеличить счетчик 320 б. ТЕОРИЯ ГРАФОВ Ю-номеров на 1 (соип1 = сомМ+ 1).
Удалить вершину е вз множества 1~~ новых вершин. Перейти на шаг 4. 4. Проверить по элементу Ьр[е], что не достигнут конец списка смежности Це] текущей вершины е. Если в списке смежности есть еще не обработанные вершины, получить иэ списка смежности очередную вершину ю, увели шть 1в[е] на 1 и перейти на шаг 6. Если список смежности Цо] вершины е обработан полностью, удалить вершину е из стека ЬТАСК и перейти на шаг 5. 5.
Если стек БТАСК пуст, вернуться на шаг 1, если иначе, то в качестве текущей вершины е взять вершину, находящуюся в вершине стека, и перейти на шаг 4. 6. Если вершина ю новая (и Е ~е), то добавить ребро (е, ш) в множество древесных ребер (З = 21 О Не, И), сделать вершину ш текущей (е = ш) и вернуться на шаг 3. Если вершина и не новая (и ф Ре), то перейти на шаг Т. Т.
Если ребра (и, ш) нет среди древесных ((е, ш) ф 21 ее), поместить ребро в список обратных ребер (Васй = Васй 0 Це, юЦ). Поместить вершину и в список Сусле. Читать содержимое стека ВТАСК, нашная с вершины стека, до появления вершины ш и помещать в список Сусеке (включая верпшну ю), т.е. формировать фундаментальный цикл, соответствующий обратному ребру 1е, ш). Добавить список Сусеке в множество фундаментальных циклов Р~ (Р, = Р, 0 (Сус1е)). Список Сус1е положить пустым (Сусеке = И). Вернуться на шаг 4. 8. Закончить работу. 5.5. Методы обхода еершшт 321 Пусть для неориентированного графа, изображенного на рис. 5.20, а, списки смежности имеют вид (5.1).
При выполнении поиска в глубину выделенные ребра являются древесными, остальные — обратными. Около каждой вершины указан присвоенный ей Р-номер. Фундаментальные циклы — в порядке их нахождения — таковы: ом оз, и,т, Оз, ит и оо, оы из, ту4, юз, ив. Поиск в глубину в неориентированном графе можно использовать и для нахождения числа его компонент. Очевидно, что зто число равно числу опустошений стека от начала до конца поиска в глубину.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
