Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 127
Текст из файла (страница 127)
Накладные расходы на инициализацию равны О (Ъ'), так что общее время работы процедуры ВРБ составляет О (к'+ Е). Таким образом, время поиска в ширину линейно зависит от размера представления графа С с использованием списков смежности. Кратчайшие пути В начале этого раздела мы говорили о том, что поиск в ширину находит расстояния до каждой достижимой вершины в графе С = (ьг, Е) от исходной вершины з Е 'ьг. Определим длину кратчайшего иувги (зпогтезг-раг(т гйзгапсе) б (з, о) от з до о как минимальное количество ребер на каком-либо пути от з к о.
Если пути от з к о не существует, то б (з, о) = со. Путь длиной Б (з, и) от з к и называется кратчайшим путем' (з)тоцезг раг)т) от з к и. Перед тем как показать, что поиск в ширину вычисляет длины кратчайших путей, рассмотрим важное свойство длин кратчайших путей. Лемма 22.1. Пусть С = (1г, Е) — ориентированный или неориентированный граф„а з е Ъ" — произвольная вершина. Тогда для любого ребра (и, и) е Е справедливо соотношение Б(з,о) < Б(з,и) + 1. Доказаигельство. Если вершина и достижима из з, то достижима и вершина о. В этом случае кратчайший путь из з в и не может быть длиннее, чем кратчайший путь из з в и, за которым следует ребро (и, о), так что указанное неравенство выполняется.
Если же вершина и недостижима из вершины з, то Б(з, и) = со и неравенство выполняется и в этом случае. Мы хотим показать, что процедура ВгБ корректно вычисляет г1 [и[ = б(з, и) для каждой вершины о Е $'. Сначала покажем, что 0 [и[ ограничивает д(з, о) сверху. гВ главах 24 и 25 мы обобщим понятие кратчайшего пути лля взвешенных графов, в которых каждое ребро имеет вес, выраженный действительным числом, а вес пути равен весу составляющих его ребер. Графы, рассматриваемые в данной главе, являются иевзвешеииыми (или, что то же самое, все ребра имеют единичный вес).
Часть Ч1 Алгоритмы для работы с графами 618 Лемма 22.2. Пусть С = (У,Е) — ориентированный или неориентированный граф, и пусть процедура ВРБ выполняется над ним с исходной вершиной з Е Е Ъ'. Тогда по завершении процедуры для каждой вершины и Е Ъ' значение Н [и], вычисленное процедурой ВРБ, удовлетворяет неравенству Н [и) > б (з, и). Доказатааьсагво. Используем индукцию по количеству операций ЕМООЛОП.
Наша гипотеза индукции заключается в том, что для всех и Е Ъ' выполняется условие И[и) > б(з,и). Базисом индукции является ситуация непосредственно после внесения з в очередь в строке 9 процедуры ВРБ. В этой ситуации гипотеза индукции справедлива, поскольку г1 [з) = 0 = б (з, з), а для всех и е Ъ' — (з) г1 [и) = оо > б (з, и). На каждом шаге индукции рассмотрим белую вершину и, которая открывается в процессе поиска из вершины и. Согласно гипотезе индукции, Н [и) > б(з, и).
На основании присвоения в строке 15 и леммы 22.1, получаем: Н [и] = И [и) + 1 > б (з, и) + 1 > б (з, и) . После этого вершина и вносится в очередь. Поскольку она при этом окрашивается в серый цвет, а строки 14-17 выполняются только для белых вершин, рассмотренная вершина и больше в очередь поставлена не будет. Таким образом, ее значение Н [и] также больше не изменяется, так что гипотеза индукции выполняется. Для доказательства того что Н [и] = б (з, и), мы должны сначала более точно разобраться, как работает очередь Я в процедуре ВРБ.
Следующая лемма показывает, что в любой момент времени в очереди находится не более двух различных значений Н. Лемма 22.3. Предположим, что в процессе выполнения процедуры ВРБ над графом С = (К Е) очередь Я содержит вершины (им из,..., сг), где из — голова очереди Я, а иг — ее хвост. Тогда для всех г = 1, 2,..., г — 1 справедливы соотношения Н[сг] < И[и~)+1 и г([и;] < г([и;+з]. Доказагаальсагво. Доказательство использует индукцию по числу операций с очередью. Изначально, когда в очереди содержится только одна вершина з, лемма определенно выполняется.
На каждом шаге индукции мы должны доказать, что лемма выполняется как после помещения вершины в очередь, так и после извлечения ее оттуда. Если из очереди извлекается ее голова из, новой головой очереди становится вершина из (если очередь после извлечения очередной вершины становится пустой, то лемма выполняется исходя из того, что очередь пуста). В соответствии с гипотезой индукции, И[и~] < г([из]. Но тогда мы имеем д [из] < И[и~]+ 1 < 0[из]+ 1, а все остальные неравенства не изменяются. Следовательно, лемма справедлива, когда новой головой очереди становится из. Глава 22. Элементарные алгоритмы для работы с графами 619 Внесем в очередь вершину в строке 17 процедуры ВРБ. При этом она становится вершиной о,.ь~.
В этот момент времени вершина и, список смежности которой сканируется, уже удалена из очереди, так что, согласно гипотезе индукции, для новой головы очереди ог выполняется неравенство а [от] > 0 [и]. Следовательно, а' [о,+т] = Н [о] = а' [и] + 1 < Н [ог] + 1. Кроме того, согласно гипотезе индукции, а [о„] < с( [и] + 1, так что т( [о„] < с( [и] + 1 = с( [о] = Н [о,ь г], а остальные неравенства остаются неизменными.
Следовательно, лемма выполняется при внесении в очередь новой вершины. Приведенное ниже следствие показывает, что значения И вносимых в очередь вершин монотонно возрастают. Следствие 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, мы заключаем, что каждый такой путь является кратчайшим. Приведенная далее процедура выводит все вершины на пути из з в о исходя из предположения, что дерево поиска в ширину уже построено процедурой ВРИ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
