Алгоритмы - построение и анализ (1021735), страница 125
Текст из файла (страница 125)
раздел 10.1) для работы с множеством серых вершин: ВРБ(С, в) 1 1ог (для) каждой вершины и Е Ъ'[С] — в г до со1ог[и] ьчн!ти 3 г([и] +- оо 4 я[и] +- ьгП. 5 со1ог[в] — пкА~' б 0[в] < — 0 я[в] — ьгп. Глава 22. Элементарные алгоритмы для работы с графами 615 Г ') .] а й — ® ":3 — 1=.) а ~ г Ц ]ы]г ] г г ~ а ГЖ2 ф' 2 2 а В х Ц Ях~, т) Е г ,'(~ (х~ Р а' Х у г 1 а и 1,— Я 1 ~ х] т '~ а ] ц Г "~у", 1 1 а х ) / а ! 1! Е ,и ЯФ ] а а т Г ~Д и и в а г Рис. 22.3. Выполнение процедуры ВРЕ над неорнентнрованным графом 8 Я+-9 9 ЕЖ~Х1ЕСЕЯ, з) 10 ттЬНе Я ф 6 11 Йо и РЕОиЕБЕ(Я) 12 1ог (для) каждой э Е "Цт'1и] 13 йо Ы со1ог~и] = тти1те 14 11геи со1ог'(п] — Пину 15 Н(о] — И]и] + 1 16 И 17 ЕХ(ЙЗЕБЕ(1Е'ф о) 18 со1ог(и] - ВЬАСК На рис.
22.3 проиллюстрирована работа процедуры ВРБ. Внутри каждой вершины графа и приведено значение И[и], а состояние очереди Я показано на Часть Ч1. Алгоритмы для работы с графами 616 момент начала каждой итерации цикла тт)п1е в строках 10-18. Рядом с элементами очереди показаны расстояния до юрия. Процедура ВРИ работает следующим образом.
В строках 1-4 все вершины, за исключением исходной вершины з, окрашиваются в белый цвет, для каждой вершины и полю д [и] присваивается значение оо, а в качестве родителя для каждой вершины устанавливается хп.. В строке 5 исходная вершина а окрашивается в серый цвет, посюльку она рассматривается как открытая в начале процедуры. В строке 6 ее полю д[а] присваивается значение О, а в строке 7 ее родителем становится мп.. В строках 8-9 создается пустая очередь Я, в которую помещается один элемент ж Цикл тт)з11е в строках 10-18 выполняется до тех пор, пока остаются серые вершины (т.е. открытые, но списки смежности которых еще не просмотрены).
Инвариант данного цикла выглядит следующим образом: При выполнении проверки в строке 10 очередь Я состоит из множе- ства серых вершин. Хотя мы не намерены использовать этот инвариант для'доказательства корректности алгоритма, легко увидеть, что он выполняется перед первой итерацией и что каждая итерация цикла сохраняет инвариант. Перед первой итерацией единственной серой вершиной и единственной вершиной в очереди Я, является исходная вершина а. В строке 11 определяется серая вершина и в голове очереди ф которая затем удаляется из очереди.
Цикл (ог в строках 12-17 просматривает все вершины о в списке смежности и. Если вершина и белая, значит, она еще не открыта, и алгоритм открывает ее„выполняя строки 14-17. Вершине назначается серый цвет, дистанция и' [о] устанавливается равной о [и] + 1, а в качестве ее родителя указывается вершина и. После этого вершина помещается в хвост очереди Я. После того как все вершины из списка смежности и просмотрены, вершине и присваивается черный цвет.
Инвариант цикла сохраняется, так как все вершины, которые окрашиваются в серый цвет (строка 14), вносятся в очередь (строка 17), а вершина, которая удаляется из очереди (строка 11), окрашивается в черный цвет (строка 18). Результат поиска в ширину может зависеть от порядка просмотра вершин, смежных с данной вершиной, в строке 12. Дерево поиска в ширину может варьироваться, но расстояния о, вычисленные алгоритмом, не зависят от порядка просмотра (см. упражнение 22.2-4).
Анализ Перед тем как рассматривать различные свойства поиска в ширину, начнем с самого простого — оценки времени работы алгоритма для входного графа С = = (К,Е). Мы воспользуемся групповым анализом, описанным в разделе 17.1. Глава 22. Элементарные алгоритмы для работы с графами 617 После инициализации ни одна вершина не окрашивается в белый цвет, поэтому проверка в строке 13 гарантирует, что каждая вершина вносится в очередь не более одного раза, а следовательно, и удаляется из очереди она не более одного раза. Операции внесения в очередь и удаления из нее требуют О(1) времени, так что общее время операций с очередью составляет О (ьг). Поскольку каждый список смежности сканируется только при удалении соответствующей вершины из очереди, каждый список сканируется не более одного раза.
Так как сумма длин всех списков смежности равна 9 (Е), общее время, необходимое для сканирования списков, равно О (Е). Накладные расходы на инициализацию равны О (Ъ'), так что общее время работы процедуры ВРБ составляет О (к'+ Е). Таким образом, время поиска в ширину линейно зависит от размера представления графа С с использованием списков смежности. Кратчайшие пути В начале этого раздела мы говорили о том, что поиск в ширину находит расстояния до каждой достижимой вершины в графе С = (ьг, Е) от исходной вершины з Е 'ьг. Определим длину кратчайшего иувги (зпогтезг-раг(т гйзгапсе) б (з, о) от з до о как минимальное количество ребер на каком-либо пути от з к о. Если пути от з к о не существует, то б (з, о) = со.
Путь длиной Б (з, и) от з к и называется кратчайшим путем' (з)тоцезг раг)т) от з к и. Перед тем как показать, что поиск в ширину вычисляет длины кратчайших путей, рассмотрим важное свойство длин кратчайших путей. Лемма 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 процедуры ВРБ. При этом она становится вершиной о,.ь~. В этот момент времени вершина и, список смежности которой сканируется, уже удалена из очереди, так что, согласно гипотезе индукции, для новой головы очереди ог выполняется неравенство Ы [от] > Н [и]. Следовательно, Н [о,+т] = Н [о] = Н [и] + 1 < Н [ог] + 1.
Кроме того, согласно гипотезе индукции, а [о„] < с( [и] + 1, так что т( [о„] < сК [и] + 1 = сК [о] = Н [о,ь г], а остальные неравенства остаются неизменными. Следовательно, лемма выполняется при внесении в очередь новой вершины. Приведенное ниже следствие показывает, что значения И вносимых в очередь вершин монотонно возрастают.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
