Алгоритмы - построение и анализ (1021735), страница 127
Текст из файла (страница 127)
Подграф предшествования поиска в глубин образует лес поиска в глубину (бер)Ь- бгз[ 1Ьгез1), который состоит из нескольких деревьев поиска в глубину (г)ерй-бгз) пеев). Ребра в Е называются ребрами дерева (ггее ег)яез). Как и в процессе выполнения поиска в ширину, вершины графа раскрашиваются в разные цвета, свидетельствующие о их состоянии. Каждая вершина изначально белая, затем при ошкрыягии (гйзсочег) в процессе поиска она окрашивается в серый цвет, и по завершении (ЙшзЬ), когда ее список смежности полностью сканирован, она становится черной.
Такая методика гарантирует, что каждая вершина в конечном счете находится только в одном дереве поиска в глубину, так что деревья не пересекаются. Помимо построения леса поиска в глубину, поиск в глубину также проставляет в вершинах мешки времени (1ппезгашр). Каждая вершина имеет две такие метки — первую г1 [и], в которой указывается, когда вершина и открывается (и окрашивается в серый цвет), и вторая — у [и], которая фиксирует момент, когда поиск завершает сканирование списка смежности вершины и и она становится черной.
Эти метки используются многими алгоритмами и полезны при рассмотрении поведения поиска в глубину. Приведенная ниже процедура ПРБ записывает в поле Н [и] момент, когда вершина ы открывается, а в поле у [и] — момент завершения работы с вершиной и. Эти метки времени представляют собой целые числа в диапазоне от 1 до 2 [У[, поскольку для каждой из [У[ вершин имеется только одно событие открытия и одно — завершения. Для каждой вершины и г1 [ы] (,1 [тг]. (22.2) До момента времени гг [и] вершина имеет цвет ьчн)тй, между б [и] и 1 [и] — цвет окАч, а после у [и] — цвет вьАск. Далее представлен псевдокод алгоритма поиска в глубину. Входной граф С может быть как ориентированным, так и неориентированным. Переменная Ите— глобальная и используется нами для меток времени.
вершин. Хатя конпептуальио поиск в ширину может выполняться из нескольких исходных вершин, а поиск в глубину — быть ограниченным одной исходной вершиной, такой подход отражает типичное использование результатов поиска. Поиск в ширину обычно используется для определения длин кратчайших путей (и связанного с ними графа предшествования) из данной вершины. Поиск в глубину, как мы увидим позже в этой главе, чаще используется в качестве подпрограммы в других алпзритмах. 624 Часть Ч1. Алгоритмы для работы с графами 13РБ(С) ! !ог (Для) каждой вершины и Е Ъ'[6] 2 по со1ог[и] — Ч~Н!тн 3 п[и] — нН. 4 ггте ~ — О 5 1ог (Для) каждой вершины и Е ~'[С] 6 оо Ы со1ог[и] = тон!те 7 1Ьеп ПРБ Чтят(и) 13РБ Нидт(и) ! со1ог[и] окАу с Открыта белая вершина и 2 рте — Йте+1 3 Й[и] — рте 4 1ог (Для) каждой вершины о Е Ад1'[и] о.
Исследование ребра (и, о). 5 оо Ы со1ог[о] = тун!те 6 тйеп я[о] — и 7 13РБ Чплт(и) 8 со1ог[и] — ВЕАСК с Завершение 9 Ди] +- рте — 1ггпе+1 На рис. 22.4 проиллюстрировано выполнение процедуры 13РБ над графом, приведенном на рис. 22.2. Ребра, исследованные алгоритмом„либо закрашены (если этот ребра деревьев), либо помечены пунктиром (в противном случае). Ребра, не являющиеся ребрами деревьев, помечены на рисунке буквами В (обратные— Ьас!с), Р (прямые — Гогтвагд) и С (перекрестные — егозя).
В вершинах указаны метки времени в формате открытие/завершение. Процедура ПРБ работает следующим образом. В строках 1-3 все вершины окрашиваются в белый цвет, а их поля я инициализируются значением н!е. В строке 4 выполняется сброс глобального счетчика времени. В строках 5-7 поочередно проверяются все вершины из Ъ', и когда обнаруживается белая вершина, она обрабатывается при помощи процедуры ЭРБ Ч!шт.
Каждый раз при вызове процедуры !3РБ Ч!щт(и) в строке 7, вершина и становится корнем нового дерева леса поиска в глубину. При возврате из процедуры 0РБ каждой вершине и сопоставляются два момента времени — время открытия (Йзсотегу бэппе) Н [и] и время завершения (Йп!зЬ1пя аппо) 7" [и]. При каждом вызове ПРБ Ч!шт(и) вершина и изначально имеет белый цвет. В строке 1 она окрашивается в серый цвет, в строке 2 увеличивается глобальная переменная Вте, а в строке 3 выполняется запись нового значения переменной ггтпе в поле времени открытия д [и].
В строках 4-7 исследуются все вершины, смежные с и, и выполняется рекурсивное посещение белых вершин. При рассмотрении в строке 4 вершины о е Аф [и], мы говорим, что ребро (и, о) исследуется (ехр!отед) поиском в глубину. И наконец, после того как будут исследованы все Глава 22. Элементарные алгоритмы для работы с графами 625 а Г) Ф )я г ) з ф~ф93йф$ ~:л 'уе)~у'7 3 Рис. 22.4.
Выполнение алгоритма поиска в глубину РРБ нал ориентированным графом ребра, покидающие и, в строках 8-9 вершина и окрашивается в черный цвет, а в поле 7' ~и1 записывается время завершения работы с ней. Заметим, что результат поиска в глубину может зависеть от порядка, в котором выполняется рассмотрение вершин в строке 5 процедуры РРБ, а также от порядка посещения смежных вершин в строке 4 процедуры РРБ Ч~з1т. На практике это обычно не вызывает каких-либо проблем, так как обычно эффективно использован может быть любой результат поиска в глубину, приводя по сути к одинаковым результатам работы алгоритма, опирающегося на поиск в глубину. Чему равно время работы процедуры РРБ? Циклы в строках 1 — 3 и 5 — 7 процедуры РРБ выполняются за время 9(У), исключая время, необходимое для вызова процедуры РРБ Чипт. Как и в случае поиска в ширину, воспользуемся групповым анализом.
Процедура 0РБ Чв~т вызывается ровно по одному разу для каждой вершины о е Ъ', так как она вызывается только для белых вершин, и первое, что она делает, — это окрашивает переданную в качестве параметра вершину в серый цвет. В процессе выполнения РРБ Чцит(о) цикл в строках 4-7 Часть ЧЕ Алгоритмы для работы с графами 626 выполняется [Аф (и] [ раз. Поскольку [Аф [и][ = 6 (Е), вел' общая стоимость выполнения строк 4 — 7 процедуры ПРБ Ч1вгг равна О (Е).
Время работы процедуры ПРБ, таким образом, равно О (У+ Е). Свойства Поиска в глубину Поиск в глубину дает нам важную информацию о структуре графа. Вероятно, наиболее фундаментальное свойство поиска в глубину заключается в том, что подграф предшествования С образует лес деревьев, поскольку структура деревьев поиска в глубину в точности отражает структуру рекурсивных вызовов процедуры 0РБ Ч!вгГ. То есть и = к (и] тогда и только тогда, когда ПРБ Ч|вгг(и) была вызвана при сканировании списка смежности вершины и.
Кроме того, вершина в является потомком вершины и в лесу поиска в глубину тогда и только тогда, когда вершина и была серой в момент открытия вершины и. Еще одно важное свойство поиска в глубину заключается в том, что времена открытия и завершения образуют скабачаую саврукавуру (рагешлев1в вппсшге). Если мы представим открытие вершины и при помощи отрывающейся скобки "(и", а завершение — при помощи закрывающейся скобки "и)", то перечень открытий и завершений образует корректное выражение в смысле вложенности скобок. Например, поиск в глубину на рис.
22.5а соответствует скобочному выражению на рис. 22.5б. Еще одно утверждение о скобочной структуре приведено в следующей теореме. Теорема 22.7 (Теорема о скобках). В любом поиске в глубину в (ориентированном или неориентированном) графе С = (У, Е) для любых двух вершин и и с выполняется ровно одно из трех следующих утверждений. ° Отрезки [0[и], 7 [и]] и [о[и], Г'[и]] не пересекаются, и ни и не является потомком и в лесу поиска в глубину, ни и не является потомком и. ° Отрезок (И(и], ДиЦ полностью содержится в отрезке (сЦи], 7" [и]], и и является потомком и в дереве поиска в глубину.
° Отрезок (И[и], 7" [и]] полностью содержится в отрезке (а[и], 7" [и]], и и является потомком и в дереве поиска в глубину. Доказательство. Начнем со случая, когда И [и] < Н (и]. При этом нам надо рассмотреть два подслучая, в зависимости от того, справедливо неравенство П [и] < < У [и] или нет. Первый подслучай соответствует справедливости неравенства а' (и] < 7" (и], так что вершина и была открыта, когда вершина и была окрашена Глава 22.
Элементарные алгоритмы для работы с графами 627 3 4 5 6 ) 8 9 )0 1) )з )3 )4 )з !ь О (г )у ,'х к ) у) )в в ) г) г) () Н ~ ) ) и в ) Рис. 22.5. Свойства поиска в гпубииу в серый цвет. Отсюда следует, что о является потомком и. Кроме того, поскольку вершина о открыта позже, чем и, перед тем как вернуться для завершения поиска к вершине и, алгоритмом будут исследованы все выходящие из )) ребра. В таком случае, следовательно, отрезок [о[о], Г"[))]] полностью содержится в отрезке [И[и], Г" [и]].
В другом подслучае у [и] < И [о], и из неравенства следует, что отрезки [И[и], Г[и]] и фо], ~[э]] не пересекаются. Посшльку отрезки не пересекаются, не происходит открьггие одной вершины, пока другая имеет серый цвет, так что ни одна вершина не является потомком другой.
Часть Ч1. Алгоритмы для работы с графами 628 Случай, когда с([и) < а [и), рассматривается аналогично, происходит только смена ролей и и ю Следствие 22.8 (Вложенность интервалов потомков). Вершина и является потомком и (отличным от самого и) в лесу поиска в глубину в (ориентированном нли неориентированном) графе С тогда и только тогда, когда а [и] < ц [и) < з [и] < < Х [и]. Доказаазельсглео. Непосредственно вытекает из теоремы 22.7. Следующая теорема дает еще одну важное указание о том, когда одна вершина в лесу поиска в глубину является потомком другой. Теорема 22.9 (Теорема о белом пути).
В лесу поиска в глубину (ориентированного или неориентированного) графа С = (1; Е) вершина и является потомком вершины и тогда и только тогда, когда в момент времени а' [и] (открытне вершины и) вершина и достижима из и по пути, состоящему только из белых вершин. Доказаагельсзаео. =ь: Предположим, что и является потомком и. Пусть ю — произвольная вершина на пути между и н и в дереве поиска в глубину, так что и является потомком и. Согласно следствию 22.8, а [и] < а [ю), так что в момент времени с( [и] вершина ю — белая. с=: Предположим, что в момент времени а'[и) вершина и достижима нз и вдоль пути, состоящего из белых вершин, но и не становится потомком и в дереве поиска в глубину.
Без потери общности предположим, что все остальные вершины вдоль пути становятся потомками и (в противном случае в качестве и выберем на пути ближайшую к и вершину, которая не становится потомком и). Пусть ю— предшественник и на пути, так что ю является потомком и (ю и и могут быть в действительности одной вершиной) и, согласно следствию 22.8, г" [ю) < ~ [и).
заметим, что вершина и должна быть открыта после того, как открыта и, но перед тем, как завершена обработка ю. Таким образом, Н [и] < г([и] < г" [ю] < з' [и]. Из теоремы 22.7 следует, что отрезок [г([и), Г" [и]] полностью содержится внутри отрезка [с1[и), г" [и]]. Согласно следствию 22.8, вершина и должна в конечном итоге быть потомком вершины и.
И Классификация ребер Еще одно интересное свойство поиска в глубину заключается в том, что поиск может использоваться для классификации ребер входного графа С = ()г, Е). Эта классификация ребер может использоваться для получения важной информации о графе. Например, в следующем разделе мы увидим, что ориентированный граф ацикличен тогда и только тогда, когда при поиске в глубину в нем не обнаруживается "обратных" ребер (лемма 22.11). Глава 22. Элементарные алгоритмы для работы с графами 629 Мы можем определить четыре типа ребер с использованием леса С , полученного при поиске в глубину в графе С.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
