Алгоритмы - построение и анализ (1021735), страница 126
Текст из файла (страница 126)
Следствие 22.4. Предположим, что вершины о, и о вносятся в очередь в процессе работы процедуры ВРЯ и что о; вносится в очередь до о . Тогда в момент внесения в очередь вершины оз выполняется неравенство Н [о,] < Н [о ]. Двказаглельсагво. Доказательство вытекает непосредственно из леммы 22.3 и того факта, что каждая вершина получает конечное значение Н в процессе выполнения процедуры ВРИ не более одного раза. Теперь мы можем доказать, что методом поиска в ширину корректно определяются длины кратчайших путей. Теорема 22.5 (Корректность поиска в ширину).
Пусть С = (1~ Е) — ориентированный или неориентированный граф, и пусть процедура ВРЯ выполняется над графом С с определенной исходной вершиной ж Тогда в процессе работы ВРЯ открывает все вершины о Е У, достижимые нз в, и по окончании работы для всех о Е Ъ' И [о] = б (в, о). Кроме того, для всех достижимых из в вершин о ф в, один из кратчайших путей от в к о — это путь от в к тг [о], за которым следует ребро (тг [о], о). Доказатаельстава.
Предположим, с целью использовать доказательство от обратного, что у некоторой вершины значение д не равно длине кратчайшего пути. Пусть о — вершина с минимальной длиной б(в,о) среди вершин, у которых оказывается неверным вычисленное значение а'. Очевидно, что о ф в. Согласно лемме 22.2, И[о] > б (в, о), так что, в силу нашего исходного предположения, И [о] > б (в, о).
Вершина о должна быть достижима из в, потому что если это не так, то б (в, о) = оо > а'[о]. Пусть и — вершина, непосредственно предшествующая о на кратчайшем пути от в к о, так что б (в, о) = б (в, и) + 1. Так как б (в, и) < б (в, о) и в силу нашего выбора вершины, о а [и] = б (в, и). Объединяя полученные результаты, имеем: И[о] > б(в,о) = б(в и)+1 = И[и]+ 1. (22.1) Часть Ч1.
Алгоритмы для работы с графами 620 Теперь рассмотрим момент, когда процедура ВРБ удаляет узел и из очереди Я в строке 11. В этот момент вершина гг может быть белой, серой или черной. Мы покажем, что для каждого из этих случаев мы получим противоречие с неравенством (22.1). Если с белая, то в строке 15 выполняется присвоение г( [с] = г( [и]+ 1, противоречащее (22.1). Если гг — черная, то она уже удалена из очереди и, согласно следствию 22.4, г( [с] < г1 [и], что опять-таки противоречит (22.1). Если с — серая, то она была окрашена в этот цвет при удалении из очереди неюторой вершины и, которая была удалена ранее вершины и и для которой выполняется равенство г1 [с] = г1 [и] + 1.
Однако из следствия 22.4 вытекает, что Н [ю] < г1 [и], поэтому г( [гг] < г1 [н] + 1, что тоже противоречит (22.1). Итак, мы заключили, что г1 [с] = б (в, с) для всех с е У. Процедурой должны быть открыты все достижимые из в вершины, потому что если это не так, то они будут иметь бесюнечное значение г(. Для завершения доказательства теоремы заметим, что если я [с] = и, то г( [гг] = г1 [и]+1. Следовательно, мы можем получить кратчайший путь из в в с, взяв кратчайший путь из в в я [с] и затем проходя по ребру (я [с], с). й Деревья Поиска в ширину Процедура ВРИ строит в процессе обхода графа дерево поиска в ширину, как показано на рис.
22.3. Дерево представлено при помощи поля я в каждой вершине. Говоря более формально, для графа С = (К Е) с исходной вершиной в мы определяем подграгр предшествованип (ргейесеззог зпЬйгврЬ) графа С как С„= (К„Е„), где ~л — — (н Е Ъ": я [гг] Ф ГЧП.) О (в) Юг = 1(Я [гг] ) с) ° гг Е ~л (вЦ ° Подграф предшествования С является деревом поиска в ширину (ЬгеагЬЬ-бгзг ггее), если Ъ' состоит из вершин, достижимых из в, и для всех с е У„в С, имеется единственный простой путь из в в с, такой что он одновременно является кратчайшим путем из в в с в С. Дерево поиска в ширину является деревом, поскольку оно является связным и ]Е ] = ٠— 1 (см. теорему Б.2). Ребра в Е, называются ребрами дерева (ггее ег(яез).
Следующая лемма показывает, что после выполнения процедуры ВРБ над графом С с исходной вершиной в подграф предшествования представляет собой дерево поиска в ширину. Лемма 22.6. Будучи примененной к ориентированному или неориентированному графу С = (К Е), процедура ВРБ строит я так, что подграф предшествования С = ()г, Е ) является деревом поиска в ширину. Глава 22.
Элементарные алгоритмы для работы с графами 621 Доказательство. В строке 16 процедуры ВРЯ присвоение к [с] = и выполняется тогда и толью тогда, когда (и, тг) е Е и б (а, с) < оо, т.е. если с достижимо из ж Следовательно, Ъ' состоит из вершин У, достижимых из а. Поскольку С образует дерево, согласно теореме Б.2 оно содержит единственный путь из а в каждую вершину множества К,.
Индуктивно применяя теорему 22.5, мы заключаем, что каждый такой путь является кратчайшим. Приведенная далее процедура выводит все вершины на пути из з в о исходя из предположения, что дерево поиска в ширину уже построено процедурой ВРИ. РК!ХТ РАТН(С, а, с) 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 Подграф нредшествования (ргебесеззог зпЬйгарЬ) поиска в глубину, таким образом, несколько отличается от такового для поиска в ширину. Мы определяем его как граф С = (У, Е )„где Е„= ((зг[и],п): не У и тг [и] ~ )чш).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
