Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 139
Текст из файла (страница 139)
Взаимоотношения предков и потомков определяются в дереве поиска в ширину как обычно: если и находится на простом пути от корня а к вершине и, то и является предком и, а и — потомком и. Приведенная ниже процедура поиска в ширину ВРБ предполагает, что входной граф С = (Г, Е) представлен с помощью списков смежности. Кроме того, поддерживаются дополнительные атрибуты в каждой вершине графа.
Цвет каждой вершины и Е 'ьг хранится в атрибуте и. со1от, а предшественник — в атрибуте и.н.. Если предшественника у и нет (например, если и = в или и не открыта), гразличне между серыми и черными нержинами позволяет легче разобраться в работе алгоритма поиска в мирилу. В действительности, как показано в упр. 22 2.3, тот же результат мыкно получить, если не различать серые и черные вершины. Часть КХ Алгоритмы для работы с графами то и. я = гчп..
Расстояние от а до вершины и, вычисляемое алгоритмом, хранится в атрибуте и. г(. Для работы с множеством серых вершин алгоритм использует очередь Я (см. раздел 10.1). ВР8(С, о) ! 1ог Каждой вершины и Е С. 1' — (б) 2 и. со!от = цгп1тЕ 3 и.г( = оо 4 гьк = гчп. 5 а.со1ог = Ока 6 з.с( = 0 7 а.я = 1ЧП. 8 Я=9 9 Еьг0глепеЯ, з) 10 згЬйе Я ~ И 1! и = 13ЕЯГлЕГлЕ(гьг) 12 зог Каждой вершины о Е С. А4 [и[ 13 11 и. Со!от == цгН!ТЕ 14 о. С01ог = пкАу !5 о.г( = и.0+1 !6 и.гг = и 17 ЕгчппепеЯ, о) 18 и.
со1ог. = веяск На рис. 22.3 продемонстрировано применение процедуры ВРБ. Процедура ВГБ работает следующим образом. В строках 1-4 все вершины, за исключением исходной вершины з, окрашиваются в белый цвет, для каждой вершины и атрибуту и, г( присваивается значение оо, а в качестве родителя для каждой вершины устанавливается гчп.. В строке 5 исходная вершина я окрашивается в серый цвет, поскольку она рассматривается как открытая в начале процедуры. В строке 6 ее атрибуту з. г( присваивается значение О, а в строке 7 ее родителем становится гчп..
В строках 8 и 9 создается пустая очередь Я, в которую помещается единственная вершина ж Цикл ьи!гИе в строках 10-18 выполняется до тех пор, пока остаются серые вершины (т.е. открытые вершины, списки смежности которых еще не просмотрены). Инвариант данного цикла выглядит следующим образом. При выполнении проверки в строке 10 очередь („Г состоит из множества серых вершин. Хотя мы не намерены использовать этот инвариант для доказательства корректности алгоритма„легко увидеть, что он выполняется перед первой итерацией и что каждая итерация цикла сохраняет инвариант. Перед первой итерацией единственной серой вершиной и единственной вершиной в очереди ь„г является исходная вершина а.
В строке 11 определяется серая вершина и в голове очереди Я, которая затем удаляется из очереди. Цикл зог в строках 12 — 17 просматривает все вершины о в списке смежности и. Если вершина о белая, значит, она еще не открыта. )лава гг. Эвементарные авгоритмы для работы с графами б33 г в ( и (в) ! г и" л у г в г и ггг и л у г в ! и Ц )у 3 (:в) (э] у и' .т (и) г и л Рнс. 223.
Выполнение процедуры ВРБ для неориентированного графа. Ребра дерева, добашшемые процедурой ВРИ, заштрихованы. В кшкдой вершине и показано соответствующее значение атрнбуга и.б. Сосптнне очереди (2 показано на момент начала кшкдой итерации цикла ыййе в строках 10-18. В очереди под вершинами указаны расстояния до ннх. и алгоритм открывает ее, выполняя строки 14-17. Вершине назначается серый цвет, дистанция п. (( устанавливается равной и. ((+ 1, а в качестве ее родителя и. н указывается вершина и.
После зтого вершина помещается в хвост очереди Я. После того как все вершины из списка смежности м просмотрены, вершина м окрашивается в строке 18 в черный цвет. Инвариант цикла сохраняется, так как все вершины, которые окрашивак)тся в серый цвет (строка 14), вносятся в очередь (строка 17), а вершина, которая удаляется из очереди (строка 11), окрашивается в черный цвет (строка 18). результат поиска в ширину может зависеть от порядка просмотра вершин, смежных с данной вершиной, в строке 12. Дерево поиска в ширину при этом может варьироваться, но расстояния ((, вычисленные алгоритмом, от порядка просмотра не зависят (см.
улр. 22.2.5). (2) (в) г и' л в ( и Оэ) 1 т 2.1;.2 г в С и (е) г' и л г в г и (г) ~'г),г) -;. ~ îãæ~~~~~~~~~~~~~~ б54 Часть И. Алгоритмы для работы с графами Анализ Перед тем как рассматривать различные свойства поиска в ширину, начнем с самого простого — оценки времени работы алгоритма для входного графа С = ()г, Е). Мы воспользуемся групповым анализом, описанным в разделе 17.! . После инициализации ни одна вершина не окрашивается в белый цвет, так что проверка в строке 13 гарантирует, что каждая вершина вносится в очередь не более одного раза, а следовательно, и удаляется из очереди она не более одного раза.
Операции внесения в очередь и удаления из нее требуют времени 0(1), поэтому общее время операций с очередью составляет 0(ьг). Поскольку каждый список смежности сканируется только при удалении соответствующей вершины из очереди, каждый список сканируется не более одного раза. Так как сумма длин всех списков смежности равна Е5(Е), общее время, необходимое для сканирования списков, равно 0(Е). Накладные расходы на инициализацию равны 0(Ъ'), так что общее время работы процедуры ВРБ составляет 0($'+ Е).
Таким образом, время поиска в ширину линейно зависит от размера представления графа С с использованием списков смежности. Кратчайшие пути В начале этого раздела мы говорили о том, что поиск в ширину находит расстояния до камсдой достижимой вершины в графе С = (у', Е) от исходной вершины в ш 1г. Определим длину кратчайшего пути (вЬоиевирабз ойвгапсе) б(в, и) от в до и как минимальное количество ребер на любом из путей от в к и.
Если пути от в к и не существует, то б(в, и) = со. Путь длиной б(в, и) от в к и называется кратчайшим лутвм2 (вЬоиевГ райт) от в к и. Перед тем как показать, что поиск в ширину вычисляет длины кратчайших путей, рассмотрим важное свойство длин кратчайших путей. л ггл Пусть С = ()У, Е) является ориентированным или неориентированным графом и пусть в е 'у' — произвольная вершина. Тогда для любого ребра (и, и) ю Е б(лги) ( б(в,и)+1. До«азательство. Если вершина и достижима из в, то достижима и вершина и. В этом случае кратчайший путь из в в и не может быть длиннее, чем кратчайший путь из в в и, за которым следует ребро (и, и), так что указанное неравенство выполняется.
Если же вершина и недостижима из вершины в, то б(в, и) = ос и неравенство выполняется и в этом случае. вв главая 24 и 25 мы обобшнм понятие яратчайшепг пути для навешенных графов, в всгормя яаждое ребро имеет вес, выраженный действительным числом, а вес луги равен весу составллюшня его ребер. Графы. рассматриваемые в данной главе, являются невтвешенными 1илн, что то же самос, все ребра имеют единичный вес). Глава 22. Элеиеитариые алгоритмы длл работы е графами б35 Мы хотим показать, что процедура ВЕБ корректно вычисляет о. Н = б(в, и) для каждой вершины и е 1'.
Сначала покажем, что и. е) ограничивает б(в, и) сверху. л гг.г Пусть С = (КЕ) является ориентированным или неориентнрованным графом и пусть процедура ВРБ выполняется над ним с исходной вершиной в Е Ъ'. Тогда по завершении процедуры для каждой вершины и Е Ъ" значение и. Ы, вычисленное процедурой ВЕБ, удовлетворяет неравенству е. Ы > б(в, и). Доказаеяельсвяео. Используем индукцию по количеству операций ЕмОпн5н. Наша гипотеза индукции заключается в том, что для всех и б Ъ' выполняется условие и.е( > б(в,и).
Базисом индукции является ситуация непосредственно после внесения в в очередь в строке 9 процедуры ВЕБ. В этой ситуации гипотеза индукции справедлива, поскольку в,Ы = 0 = 6(в,в), а для всех и е )г — (в) выполняется и. Н = оо > б(в, и).
На каждом шаге индукции рассмотрим белую вершину и, которая открывается в процессе поиска из вершины и, Согласно гипотезе индукции и. е) > б(в, и). На основании присвоения в строке 15 и леммы 22.! получаем и. Н = и.е) +1 > б(в,и) +1 > б(в,и) . После этого вершина и вносится в очередь. Поскольку она при этом окрашивается в серый цвет, а строки 14-17 выполняются только для белых вершин, рассмотренная вершина и больше помещаться в очередь не будет. Таким образом, ие будет изменяться и ее значение и.
И, так что гипотеза индукции выполняется. Для доказательства того, что и. «1 = б(в, и), сначала разберемся, как работает очередь Я в процедуре Вг Я. Следующая лемма показывает, что в любой момент времени в очереди находится не более двух различных значений д. л гг.з Предположим, что во время выполнения процедуры ВРЯ над графом С = (К, Е) очередь Я содержит вершины (иы из,..., ие), где щ — голова Я, а и, — ее хвост. Тогда для всех 1= 1,2,...,г — 1 выполняется и„.И < им 0+1 и соН ( ивв.1.Ы. Доказательство. В доказательстве используется индукция по числу операций с очередью.
Изначально, когда в очереди содержится только одна вершина в, лемма, определенно, выполняется. На каждом шаге индукции необходимо доказать, что лемма выполняется как после помещения вершины в очередь, так и после извлечения ее оттуда. Если из очереди извлекается ее голова ом новой головой очереди становится вершина из (если очередь после извлечения некоторой вершины становится пустой, то лемма выполняется исходя из того, что очередь пуста). В соответствии с гипотезой бзб Часеь И. Алгоритмы для работы с графами индукции иг. Ы < из.б. Но тогда мы имеем и„.И < иг.б + 1 < из.б+ 1, а все остальные неравенства не изменяются. Следовательно, лемма справедлива, когда новой головой очереди становится из. Чтобы понять, что происходит при внесении вершины в очередь, нужно рассмотреть код более подробно.
Когда мы вносим в очередь вершину и в строке 17 процедуры ВРИ, она становится вершиной и„А.г. В этот момент времени вершина и, список смежности которой сканируется, уже удалена из очереди Ь), так что согласно гипотезе индукции для новой головы иг выполняется неравенство иг. И > и. б. Таким образом, и„+г. б = и. И = и. И + 1 < ип Ы + 1. Кроме того, согласно гипотезе индукции и„. И < и. Ы+ 1, так что и„. Ы < и. 0+ 1 = и. б = и,.ьг. Ы, а остальные неравенства остаются неизменными.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
