Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 140
Текст из файла (страница 140)
Следовательно, лемма выполняется при внесении в очередь новой вершины и. Приведенное ниже следствие показывает, что значения И вносимых в очередь вершин монотонно возрастают со временем. Следствие 22.4 Предположим, что вершины иг и и вносятся в очередь в процессе работы процедуры ВРБ и что иг вносится в очередь до и . Тогда в момент внесения в очередь вершины и; выполняется неравенство иы б < и . б. Доказательство.
Доказательство вытекает непосредственно из леммы 22.3 и того факта, что каждая вершина получает конечное значение И в процессе выполнения процедуры ВРЯ не более одного раза. Теперь мы можем доказать, что метод поиска в ширину корректно определяет длины кратчайших путей. Теорема 22.5 корректность ноиска в тирану) Пусть С = (г', Е) представляет собой ориентированный или неориентированный граф, и предположим, что процедура ВРЯ выполняется над графом С с определенной исходной вершиной в е Г Тогда в процессе работы процедура ВРЯ открывает все вершины и Е Ъ', достижимые из исходной вершины в, а по окончании работы для всех и е К справедливо равенство и. И = б(в, и). Кроме того, для всех достижимых из в вершин и Ф в один из кратчайших путей от в к и— это путь от в к и.
гг, за которым следует ребро (и. гг, и). Доказательство. Предположим, с целью использовать доказательство от обратного, что у некоторой вершины значение гг не равно длине кратчайшего пути. Пусть и — вершина с минимальной длиной пути б(в,и) среди вершин, для которых оказывается неверным вычисленное значение И.
Очевидно, что и ф в. Согласно лемме 22.2 и, б > б(в, и), так что в силу нашего исходного предположения и.б > б(в,и). Вершина и должна быть достижима из в, потому что, если это не так, б(в, и) = оо > и. Ы. Пусть и — вершина, непосредственно предшествующая и на кратчайшем пути от в к и, так что б(в,и) = б(в, и) + 1.
Поскольку б(в, и) < б(в, и), в силу нашего выбора вершины и выполняется условие Главадй Элементарные алгоритмы длл работы с градами б37 и. Н = б(в, и). Обьединив полученные результаты, имеем о.Н > б(в,о) = б(в,и) +1 = и.0+ 1 (22.1) Теперь рассмотрим момент, когда процедура ВРИ удаляет узел и из очереди Я в строке 11. В этот момент вершина о может быть белой, серой или черной. Мы покажем, что для каждого из этих случаев мы получим противоречие с неравенством (22.1). Если вершина о белая, то в строке 15 выполняется присвоение о.б = и. Н + 1, противоречащее (22.1). Если о — черная вершина, то она уже удалена нз очереди и согласно следствию 22.4 о, б < и. г(, что, опять-таки, противоречит (22.!). Если о — серая вершина, то она была окрашена в этот цвет при удалении из очереди некоторой вершины ш, которая была удалена ранее вершины и и для которой выполняется равенство о. Н = ш.
Ы + 1. Однако из следствия 22.4 вытекает, что ш.Н < и.Н, поэтому о.Н = ш.0+1 < и.0+1, что также противоречит (22.1). Итак, мы заключили, что о. г( = б(в, о) для всех о ~ И. Процедурой должны быть открыты все достижимые из в вершины о, потому что, если это не так, для них будет выполняться со = о. Н > б(в, о). Для завершения доказательства теоремы заметим, что если о.
7г = и, то о. Ы = и. Н + 1. Следовательно, мы можем получить кратчайший путь из в в о, взяв кратчайший путь из в в о.л, а затем пройдя по ребру (о. а, о). Деревья поиска в ширину Процедура ВРЗ строит в процессе обхода графа дерево поиска в ширину, как показано на рис. 22.3.
Это дерево соответствует атрибутам л в каждой вершине. Говоря более формально, для графа С = (Ъ; Е) с исходной вершиной в мы определяем «адграф «ред«гесг«еоеа««я (ргедесеввог вцЬйгарЬ) графа С как С = (Ъ', Е ), где 1'и = (о Е 17 '. о. л ф М1Ь) 0 (в) Е, = ((о.7г, о): о е 17и — (в)) Подграф предшествования С является деревом «о«ока в «гири«у (Ьгеадгй-Гпзг 1гее), если И состоит из вершин, достижимых из в, и если для всех о е И в С„имеется единственный простой путь из в в о, такой что он одновременно является кратчайшим путем из в в о в С.
Дерево поиска в ширину является деревом, поскольку оно является связным и (Е ) = ٠— 1 (см. теорему Б.2). Ребра в Е называются ребрами дерева (1гее едйев). Следующая лемма показывает, что после выполнения процедуры ВРБ над графом С с исходной вершиной в подграф предшествования представляет собой дерево поиска в ширину. Части П.
Алгоритмы длл работы с грифами бзв Лемма 22.6 Будучи примененной к ориентированному или неориентированному графу С = ($; Е), процедура ВГЯ строит гг таким образом, что подграф предшествования Са = (У, Е ) является деревом поиска в ширину. Доказаагельсагво. В строке 16 процедуры ВРБ присвоение о.я = и выполняется тогда и толькотогда, когда (и,и) е Е и 6(в,о) < оо,т.е. если с достижимо из в. Следовательно, $; состоит из вершин Ъ', достижимых из в. Поскольку С образует дерево, согласно теореме Б.2 он содержит единственный путь из в в каждую вершину множества $;. Индуктивно применив теорему 22.5, мы заключаем, что каждый такой путь является кратчайшим в С.
Приведенная далее процедура выводит все вершины на кратчайшем пути из в в о в предположении, что дерево поиска в ширину уже построено процедурой ВРБ. РК1МТ-РАТН (С, в, о) ! !!о==в 2 рпп1 в 3 е!зеИ о.х == гчн. 4 рпп! "Путь из" в "в" о "отсутствует" 5 е!зе Ркгнт-РАтн(С, в, с.
л) 6 рплг с Время работы процедуры линейно зависит от количества выводимых вершин, поскольку каждый рекурсивный вызов процедуры осуществляется для пути, который на одну вершину короче текущего. Упражнения 22.2Л Покажите, какие значения г( и гг получатся в результате поиска в ширину в ориентированном графе, показанном на рис. 22.2, (а), если в качестве исходной взять вершину 3. 22.2.2 Покажите, какие значения а и я получатся в результате поиска в ширину в неориентированном графе, показанном на рис.22.3, если в качестве исходной взять вершину и.
22.2.З Покажите, что достаточно одного бита для цвета для того, чтобы процедура ВРБ давала корректный результат, доказав, что при удалении строки 1е из процедуры она будет давать тот же результат, что и с этой строкой. ба 9 Глава 22. Элементарные аыоритмы дал работы с графамн 22.2.4 Чему будет равно время работы процедуры ВРЯ, адаптированной для работы с матричным представлением графа? 22.2.5 Докажите, что при выполнении поиска в ширину значение и. Н, назначаемое вершине и, не зависит от порядка перечисления вершин в списках смежности. Используя рис.
22.3 в качестве примера, покажите, что вид дерева поиска в ширину, вычисленного с помощью процедуры ВРК, может зависеть от порядка перечисления вершин в списках смежности. 22.2. 6 Приведите пример ориентированного графа С = ($; Е), исходной вершины л е 'е' и множества ребер дерева Е С Е, таких, что для каждой вершины е е )г' единственный путь в графе ($', Е„) от в к о является кратчайшим путем в графе С, но множество ребер Е невозможно получить с помощью процедуры ВРИ ни при каком порядке вершин в списках смежности. 22.2.
7 Предположим, что есть и борцов, между любой парой которых может состояться (а может и не состояться) поединок, и список г поединков. Разработайте алгоритм, который за время 0(п+ г) определяет, можно ли разделить всех борцов на две команды так, чтобы в поединках встречались только борцы из разных команд и чтобы, если это возможно, алгоритм выполнял такое разделение. 22.2,8 * Диаметр дерева Т = (\г, Е) определяется как шаха ее~ б(и, о), т.е. диаметр— зто наибольшая длина кратчайшего пути в дереве. Разработайте эффективный алгоритм вычисления диаметра дерева и проанализируйте время его работы.
22.2.9 Пусть С = (Ь; Е) — связный неориентированный граф. Разработайте алгоритм для вычисления за время 0($'+ Е) пути в С, который проходит по каждому ребру из Е ровно по одному разу в каждом направлении. Придумайте способ выйти из лабиринта, если у вас в карманах имеется много монет. 22.3. Поиск в глубину Стратегия поиска в глубину, как следует из ее названия, состоит в том, чтобы идти "в глубь" графа, насколько это возможно. При выполнении поиска в глубину он исследует все ребра, выходящие нз вершины, открытой последней, н покидает вершину, только когда не остается неисследованных ребер — при этом происходит "откат" в вершину, из которой была открыта вершина ю.
Этот процесс продолжается до тех пор, пока не будут открыты все вершины, достижимые из исходной. 640 Часть У1 Алгоритмы для работы с графами Если при этом остаются неоткрытые вершины, то одна из них выбирается в качестве новой исходной вершины и поиск повторяется уже из нее. Этот процесс повторяется до тех пор, пока не будут открыты все вершины.з Как и в случае поиска в ширину, когда вершина и открывается в процессе сканирования списка смежности уже открытой вершины и, процедура поиска записывает это событие, устанавливая атрибут о.
я равным и. В отличие от поиска в ширину, когда подграф предшествования образует дерево, при поиске в глубину подграф предшествования может состоять из нескольких деревьев, так как поиск может выполняться из нескольких исходных вершин. Подграф предшеспавования (ргедесеааог зцЬйуврЬ) поиска в глубину, таким образом, несколько отличается от такового для поиска в ширину.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
