Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 141
Текст из файла (страница 141)
Мы определяем его как С = (ьг, Е ), где Е, = ((тг.л, тг): ч ш ) ' и ю. тг ~ У41ь) Подграф предшествования поиска в глубину образует лес поиска в глубину (дербз-(пзу гогебу), который состоит из нескольких деревьев поиска е глубину (деруь-гпз1 пеез). Ребра в е называются ребрами дерева (пес едйез). Как и в процессе поиска в ширину, вершины графа окрашиваются в разные цвета, свидетельствующие об их состоянии. Каждая вершина изначально белая, затем при ошкрывдии (гйзсочег) в процессе поиска она окрашивается в серый цвет, и по завершении, когда ее список смежности полностью просканирован, она становится черной. Такая методика гарантирует, что каждая вершина в конечном счете находится только в одном дереве поиска в глубину, так что деревья не пересекаются. Помимо построения леса поиска в глубину, поиск в глубину также проставляет в вершинах мензки времени (~ппезуашр).
Каждая вершина имеет две такие метки: первую — тг. Ы, в которой записывается, когда вершина е открывается (и окрашивается в серый цвет), и вторую — п.1, которая фиксирует момент, когда поиск завершает сканирование списка смежности вершины п и она становится черной. Эти метки используются многими алгоритмами и полезны при рассмотрении поведения поиска в глубину. Приведенная ниже процедура ПРЯ записывает в атрибут п.г( момент, когда вершина и открывается, а в атрибут и.1 — момент завершения работы с вершиной и.
Эти метки времени представляют собой целые числа в диапазоне от 1 до 2 ~Ц, поскольку для каждой из Щ вершин имеется только одно событие открытия и одно — завершения. Для каждой вершины и и. г( ( и.1 (22.2) Может показшъся нестлыш странным то, по поиск в ширину ограничен только одной исходной вершиной, в то время как поиск в глубину может выполняться из нескольких исходных вершин. Хотя конпепччшьно поиск в ширину может выполняться из нескольких исходных вершин, а поиск в глубину — быть ограниченным одной исходной вершиной, такой подход отражает типичное использование результатов поиска. Поиск в ширину обычно используется для определенна длин кратчайших путей (и связанного с ними графа прел- шествования) из данной вершины.
Поиск в глубину, как ыы увидим позже в зшй главе, чаше используется в качестве подпрограммы в друпгх алгоритмах. Глава л2. Эллмеитариые аигоритмы длл работы с графами б41 РРБ(С) 1 1ог каждой вершины и Е С. и' 2 и.со1ог = ШН1тн 3 и.я = Х1Ь 4 Нте =О 5 1ог каждой вершины и е С. $~ б 11'и, со1от == Ъ'Н1тЕ 7 РРВ-Ч1з1т(С, и) РРЗ-Ч1шт(С, и) 1 Вте = 11те+1 2 и.д = 11те 3 и.со1ог = склт 4 1ог каждой и е С.
Аа) 1и) 5 11' и. со1ог == 1й'Н1тн 6 г.п =и 7 Рг Я-Ч1З171С, и) 8 и.со1ог = ВЬАСК 9 Вте = йте+1 1О и./ = Ыте // Открыта белая вершина и // Исследование ребра (и, и) // Завершение работы с и На рис. 22.4 показана работа процедуры РР8 с графом на рис. 22.2. Процедура РРБ работает следующим образом. В строках 1-3 все вершины окрашиваются в белый цвет, а их поля я инициализируются значением н1ь. В строке 4 выполняется сброс глобального счетчика времени. В строках 5 — 7 поочередно проверяются все вершины из Ъ', и когда обнаруживается белая вершина, она обрабатывается с помощью процедуры РЕЯ-Ч1з1т. Каждый раз прн вызове процедуры Рг 8-Ч1з1т(С, и) в строке 7 вершина и становится корнем нового дерева леса поиска в глубину. При возврате из процедуры РР8 каждой вершине и сопоставляются два момента времени — время открытия (Йзсомегу йще) и.
Ы и время завернления 1йп)зЫпй 1ппе) и./. При каждом вызове РРЯ-Ч1В1т(С, и) вершина и изначально имеет белый цвет. В строке 1 увеличивается глобальная переменная 11те, в строке 2 выполняется запись нового значения переменной Нте в атрибут времени открытия и.д, а в строке 3 вершина и окрашивается в серый цвет. В строках 4-7 исследуются все вершины и, смежные с и, и выполняется рекурсивное посещение всех вершин и, являющихся белыми. При рассмотрении в строке 4 каждой вершины и Е Аа7'[и) мы говорим, что ребро (и, и) исследуется (ехр1огед) поиском в глубину. И наконец, после того как будут исследованы все ребра, покидающие и, г1 лик лгал До момента времени и. а вершина и имеет цвет щн1те, между и, а и и./ — цвет ОКАУ, а после — цвет ВЬАСК.
Далее представлен псевдокод алгоритма поиска в глубину. Входной граф С может быть как ориентированным, так и неориентированным. Переменная 11тпе— глобальная и используется нами для меток времени. Часть Иб Алгоритмы для работы с аьафаии 642 у (г) Щ~)фввк х у 1 (ь) (зк!:о е'.~:,':З ~ ) х у г (я) аД (т= (н) х (а) у у х (м) (х) ((нед ) х у у г (а) (в) (к) Х (и) Рне. 22.4. Применение алгоритма пояска в глубину ))РЯ к ориентированному графу. Исследуемые прн этом ребра показаны затененными (еслн это ребра дерева) нлн пунктирными (в противном случае).
Ребра, не являюшнеса ребрами дерева, помечены буквами В. С нлн Г в состав(станк с тем, являлася лн онн обратными (оас)г), перекрестными (сана) нлн првмымн (Еогиап)). В вершинах указаны метки времени в форьмте "аткрытвеlзаеершенне*'. в строках 8-10 вершина и окрашивается в черный цвет, а в атрибут п.у записывается время завершения работы с ней. Заметим, что результат поиска в глубину может зависеть от порядка, в котором выполняется рассмотрение вершин в строке 5 процедуры 1)ЕБ, а также от порядка посещения смежных вершин в строке 4 процедуры ПЕБ-У)шт.
На практике это обычно не вызывает каких-либо проблем, так как обычно эффективно использоваться может любой результат поиска в глубину, приводя, по сути, к одинаковым результатам работы алгоритма, опирающегося на поиск в глубину. Чему равно время работы процедуры ПЕБ? Циклы в строках 1-3 и 5-7 процедуры ОРБ выполняются за время ту( ь'), исключая время, необходимое для вызова процедуры ВРБ-У)ят. Как и в случае поиска в ширину, воспользуемся групповым анализом, Процедура куГБ-У)з)т вызывается ровно по одному разу для каждой вершины и Е Ъ", так как она вызывается только для белых вершин, а первое, что она делает, — зто окрашивает переданную в качестве параметра вершину в серый цвет.
В процессе выполнения 1)г Б-У)з)т((у, н) цикл в строках 4-7 вы- Глава 22. Элементарные алгоритмы длл работы с гра4~аии полняется ]А4[и][ раз. Поскольку ]Аф[и][ = 9(Е), общая стоимость выполнения строк 4 — 7 процедуры ПЕБ-Чнцт равна гл(Е). Вре- мя работы процедуры РЕЯ, таким образом, равно 9(Ъ'+ Е). Свойства поиска в глубину Поиск в глубину дает нам важную информацию о структуре графа.
Вероятно, наиболее фундаментальное свойство поиска в глубину заключается в том, что подграф предшествования С в действительности образует лес деревьев, поскольку структура деревьев поиска в глубину в точности отражает структуру рекурсивных вызовов процедуры ОЕБ-Чнцт. То есть и = и. и тогда и только тогда, югда РРЕ-Ч~ят(С, и) была вызвана при сканировании списка смежности вершины и. Кроме того, вершина и является потомюм вершины и в лесу поиска в глубину тогда и только тогда, когда вершина и была серой в момент открытия вершины и.
Еще одно важное свойство поиска в глубину заключается в том, что времена открытия и завершения образуют скобочиую структуру (рагепйеяз зписшге). Если мы представим открытие вершины и с помощью отрывающейся скобки "(и*', а завершение — с помощью закрывающейся скобки "и)'*, то перечень открытий и завершений образует корректное выражение в смысле вложенности скобок. Например, поиск в глубину на рис. 22.5,(а) соответствует скобочному выражению на рис. 22.5,(б).
Еще одно утверждение о сюбочной структуре приведено в следующей теореме. Теорема 22. 7 ~Теорема о скобках) В любом поиске в глубину в (ориентированном или неориентированном) графе С = (3г, Е) для любых двух вершин и и и выполняется ровно одно из трех следующих утверждений. Отрезки [и. Н, и. ) ] и [и. Н, и2] не пересекаются, и ни и не является потомком и в лесу поиска в глубину, ни и не является потомком и. Отрезок [и. И, и.Д полностью содержится в отрезке [и. с(, и.Д, а и является потомком и в дереве поиска в глубину.
Отрезок [и. И,и.т] полностью содержится в отрезке [и. И,и.2], а и является потомком и в дереве поиска в глубину. Доказавгельсшво. Начнем со случая, когда и.й ( и.гг. При этом необходимо рассмотреть два подслучая в зависимости от того, справедливо ли неравенство и.Ы < и.2. Первый подслучай соответствует справедливости неравенства и. А < и.2, так что вершина и была открыта, когда вершина и все еще была окрашена в серый цвет. Отсюда следует, что и является потомком и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
