Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 128
Текст из файла (страница 128)
РК!ХТ РАТН(С, а, с) 1 Пс=з 2 ГЬеп рппг а 3 е1зе и к[с] = ьги. 4 гпеп рппт "Путь из" а "в" о "отсутствует" 5 е1зе Ркпчт РАтн(С,з,тг[о]) б рпп1 тг Время работы процедуры линейно зависит от количества выводимых вершин, так как каждый рекурсивный вызов процедуры осуществляется для пути, юторый на одну вершину короче текущего. Упражнения 22.2-1. Покажите, какие значения г1 и тг получатся в результате поиска в ширину в ориентированном графе, показанном на рис.
22.2а, если в качестве исходной взять вершину 3. 22.2-2. Покажите, какие значения Н и к получатся в результате поиска в ширину в неориентированном графе, показанном на рис. 22.3, если в качестве исходной взять вершину и. 22.2-3. Чему будет равно время работы процедуры ВРБ, адаптированной для работы с матричным представлением графа? 22.2-4. Докажите, что при выполнении поиска в ширину значение г1 [и], назначаемое вершине и, не зависит от порядка перечисления вершин в списках смежности. Используя рис. 22.3 в качестве примера, покажите, что вид дерева поиска в ширину, вычисленного с помощью процедуры ВРБ, может зависеть от порядка перечисления вершин в списках смежности. 22.2-5.
Приведите пример ориентированного графа С = (1г, Е), исходной вершины з е У и множества ребер дерева Е С Е, таких что для каждой вершины ггпу У единственный путь в графе (У, Е ) от з к и является кратчайшим путем в графе С, но множество ребер Е„невозможно получить Часть Ч!. Алгоритмы для работы с графами 622 при помощи процедуры ВРБ ни при каком порядке вершин в списках смежности. 22.2-6. Предположим, что у нас есть и борцов, межцу любой парой которых может состояться, (а может и не состояться) поединок, и список т поединюв. Разработайте алгоритм, который за время О (и + г) определяет, можно ли разделить всех борцов на две юманды так, чтобы в поединках встречались только борцы из разных команд, н если это возможно, то алгоритм должен выполнять такое разделение.
* 22.2-7. Диаметр дерева Т = (к', Е) определяется как шах о(и,п), и,са г' т.е. диаметр — это наибольшая длина кратчайшего пути в дереве. Разработайте эффективный алгоритм вычисления диаметра дерева и проанализируйте время его работы. 22.2-8. Пусть О = (К Е) — связный неориентированный граф. Разработайте алгоритм для вычисления за время О (У+ Е) пути в С, который проходит по каждому ребру из Е по одному разу в каждом направлении. Придумайте способ выйти из лабиринта, если у вас в карманах имеется много монет. 22.3 Поиск в глубину Стратегия поиска в глубину, как следует из ее названия, состоит в том, чтобы идти "вглубь" графа, насколько это возможно.
При выполнении поиска в глубину исследуются все ребра, выходящие из вершины, открытой последней, и покидает вершину, только югда не остается неисследованных ребер — при этом происходит возврат в вершину, из которой была открыта вершина и. Этот процесс продолжается до тех пор, пока не будут открыты все вершины, достижимые из исходной. Если при этом остаются неоткрытые вершины, то одна из них выбирается в качестве новой исходной вершины и поиск повторяется уже из нее. Этот процесс повторяется до тех пор, пока не будут открыты все вершины.
Как и в случае поиска в ширину, когда вершина и открывается в процессе сканирования списка смежности уже открытой вершины и, процедура поиска записывает это событие, устанавливая поле предшественника и тг [и] равным и. В отличие от поиска в ширину, где подграф предшествования образует дерево, при поиске в глубину подграф предшествования может состоять из нескольких деревьев, так как поиск может выполняться из нескольких исходных вершинз. Может показаться несколько странным то, что поиск в ширину ограничен только одной исходной вершиной, в то время как поиск в глубину может выполняться из нескольких исходных Глава 22.
Элементарные алгоритмы для работы с графами 623 Подграф нредшествования (ргебесеззог зпЬйгарЬ) поиска в глубину, таким образом, несколько отличается от такового для поиска в ширину. Мы определяем его как граф С = (У, Е )„где Е„= ((зг[и],п): не У и тг [и] ~ )чш). Подграф предшествования поиска в глубин образует лес поиска в глубину (бер)Ь- бгз[ 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 а Г) Ф )я г ) з 4е41вв)))йфв г Рис. 22.4. Выполнение алгоритма поиска в глубину РРБ нал ориентированным графом ребра, покидающие и, в строках 8-9 вершина и окрашивается в черный цвет, а в поле 7' ~и1 записывается время завершения работы с ней. Заметим, что результат поиска в глубину может зависеть от порядка, в котором выполняется рассмотрение вершин в строке 5 процедуры РРБ, а также от порядка посещения смежных вершин в строке 4 процедуры РРБ Ч~з1т. На практике это обычно не вызывает каких-либо проблем, так как обычно эффективно использован может быть любой результат поиска в глубину, приводя по сути к одинаковым результатам работы алгоритма, опирающегося на поиск в глубину.
Чему равно время работы процедуры РРБ? Циклы в строках 1 — 3 и 5 — 7 процедуры РРБ выполняются за время 9(У), исключая время, необходимое для вызова процедуры РРБ Чипт. Как и в случае поиска в ширину, воспользуемся групповым анализом. Процедура 0РБ Чв~т вызывается ровно по одному разу для каждой вершины о е Ъ', так как она вызывается только для белых вершин, и первое, что она делает, — это окрашивает переданную в качестве параметра вершину в серый цвет. В процессе выполнения РРБ Чцит(о) цикл в строках 4-7 Часть ЧЕ Алгоритмы для работы с графами 626 выполняется [Аф (и] [ раз. Поскольку [Аф [и][ = 6 (Е), вел' общая стоимость выполнения строк 4 — 7 процедуры ПРБ Ч1вгг равна О (Е).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
