Изменения

'''Обход в ширину''' ('''Поиск в ширину, англ. ''BFS'', '', Breadth-first search'') — один из простейших алгоритмов обхода [[Основные определения теории графов|графа]], являющийся основой для многих важных алгоритмов для работы с графами. Например, алгоритм [[Алгоритм Прима|Прима]] поиска минимального остовного дерева или алгоритм [[Алгоритм Дейкстры|Дейкстры]] поиска кратчайшего пути из одной вершины используют идеи, сходные идеям, используемым при поиске в ширину.

==Описание алгоритма ==[[Image: Graph-BFS.gif|thumb|240px|АлгоритмBFS<br><font color==#3c9eff>посещенные</font> вершины<br>]]

Для отслеживания работы алгоритма поиск в ширину раскрашивает вершины графа в белый, серый и черный цвета. Изначально все вершины белые, и позже они могут стать серыми, а затем черными. Когда вершина '''открывается''' в процессе поиска, она окрашивается. Таким образом, серые и черные вершины — это вершины, которые уже были открыты, но алгоритм поиска в ширину по-разному работает с ними, чтобы обеспечить объявленный порядок обхода. Если Пусть задан невзвешенный ориентированный граф <tex>G = (uV, vE) \in E</tex> и вершина <tex>u</tex> черного цвета, то в котором выделена исходная вершина <tex>vs</tex> либо серая, либо черная. Требуется найти длину кратчайшего пути (если таковой имеется) от одной заданной вершины до другой. Частным случаем указанного графа является невзвешенный неориентированный граф, т.е. все вершиныграф, в котором для каждого ребра найдется обратное, смежные с ней уже открыты. Серые соединяющее те же вершины могут иметь белых соседей, представляя собой границу между открытыми и неоткрытыми вершинамив другом направлении.

Поиск в ширину стоит дерево поиска в ширину, которое изначально состоит из одного корня, которым является исходная вершина Для алгоритма нам потребуются [[Очередь|очередь]] и множество посещенных вершин <tex>swas </tex>. Если в процессе сканирования списка смежности уже открытое вершины , которые изначально содержат одну вершину <tex>us </tex> открывается белая вершина <tex>v</tex>, то вершина . На каждом шагу алгоритм берет из начала очереди вершину <tex>v</tex> и ребро добавляет все непосещенные смежные с <tex>(u, v)</tex> добавляются вершины в дерево. При этом <tex>u</tex> является '''предшественником''' (predecessor), или '''родителем''' (parent), <tex>vwas </tex> и в дереве поиска вширинуконец очереди. Посколько вершина модет быть открыта не более одного разаЕсли очередь пуста, она имеет не более одного родителято алгоритм завершает работу.

=== Реализация=Анализ времени работы ==Приведенная ниже процедура поиска в ширину '''BFS''' предполагает, что входной граф Оценим время работы для входного графа <tex>G = (V, E)</tex> представлен при помощи списков смежности. Кроме того, поддерживаются дополнительные структуры данных в каждой вершине графа. Цвет каждой вершины где множество ребер <tex>u \in V</tex> хранится в переменной <tex>color[u]</tex>, а предшественник — в переменной <tex>p[u]E </tex>представлено списком смежности. Если прежшественника у <tex>u</tex> нетВ очередь добавляются только непосещенные вершины, то <tex>p[u] =</tex> NILпоэтому каждая вершина посещается не более одного раза. Расстояние от <tex>s</tex> до вершины <tex>u</tex>, вычисляемое алгоритмом, хранится Операции внесения в поле <tex>d[u]</tex>. Алгоритм использует очередь и удаления из нее требуют <tex>QO(1) </tex> для времени, так что общее время работы с множеством серых вершин. '''BFS'''(очередью составляет <tex>GO(|V|) </tex>, <tex>s</tex>) 1 '''for''' (для) операций. Для каждой вершины <tex>u \in V[G] - sv </tex> 2 '''do''' рассматривается не более <tex>color[u] \leftarrow</tex> WHITE 3 <tex>d[u] \leftarrow \mathcal mathrm{1deg}(v) </tex> 4 ребер, инцидентных ей. Так как <tex>p[u] \leftarrow</tex> NIL 5 <tex>color[s] sum\leftarrow</tex> GRAY 6 <tex>d[s] limits_{v \leftarrow</tex> 0 7 <tex>p[s] in V} \leftarrow</tex> NIL 8 <tex>Q \leftarrow</tex> Ø 9 ENQUEUEmathrm{deg}(<tex>Qv) = 2|E| </tex>, то время, используемое на работу с ребрами, составляет <tex>s</tex>O(|E|) 10 '''while''' <tex>Q \ne </tex>Ø 11 '''do''' <tex>u \leftarrow. Поэтому общее время работы алгоритма поиска в ширину — </tex> DEQUEUEO(<tex>Q</tex>) 12 '''for''' (для) каждой <tex>м \in Adj[u]</tex> 13 '''do''' '''if''' <tex>color[u] =</tex> WHITE 14 '''then''' <tex>color[v] \leftarrow</tex> GRAY 15 <tex>d[v] \leftarrow d[u] |V| + 1</tex> 16 <tex>p[v] \leftarrow u</tex> 17 ENQUEUE(<tex>Q</tex>, <tex>v</tex>|E|) 18 <tex>color[u] \leftarrow</tex>BLACK.

== Анализ Корректность ==Оценим время работы для входного графа <tex>G = (V, E)</tex>. После инициализации ни одна вершина не окрашивается в белый цвет, поэтому проверка в строке 13 гарантирует, что каждая вершина вносится в очередь не более одного раза, а следовательно, и удаляется из очереди она не более одного раза. Операции внесения в очередь и удаления из нее требуют <tex>O(1)</tex> времени, так что общее время операций с очередью составляет <tex>O(V)</tex>. Поскольку каждый список смежности сканируется только при удалении соответствующей вершины из очереди, каждый список сканируется не более одного раза. Так как сумма длин всех списков смежности равна <tex> \Theta (E) </tex>, общее время, необходимое для сканирования списков, равно <tex>O(E)</tex>. Накладные расходы на инициализацию равны <tex>O(V)</tex>, так что общее время работы процедуры '''BFS''' составляет <tex>O(V + E)</tex>. Таким образом, время работы поиска в ширину линейно зависит от размера представления графа <tex>G</tex> с использованием списков смежности.

{{Утверждение|statement=В очереди поиска в ширину расстояние вершин до <tex>s</tex> монотонно неубывает.|proof=Докажем это утверждение индукцией по числу выполненных алгоритмом шагов. Введем дополнительный инвариант: у любых двух вершин из очереди, расстояние до <tex> s </tex> отличается не более чем на <tex> 1 </tex>.  '''База''': изначально очередь содержит только одну вершину <tex> s </tex>.  '''Переход''': пусть после <tex> i-й </tex> итерации в очереди <tex> a + 1 </tex> вершин с расстоянием <tex> x </tex> и <tex> b </tex> вершин с расстоянием <tex> x + 1 </tex>.  Рассмотрим <tex> i-ю </tex> итерацию. Из очереди достаем вершину <tex> v </tex>, с расстоянием <tex> x </tex>. Пусть у <tex>v</tex> есть <tex>r </tex> непосещенных смежных вершин. Тогда, после их добавления, в очереди находится <tex> a </tex> вершин с расстоянием <tex> x </tex> и, после них, <tex> b + r </tex> вершин с расстоянием <tex> x + 1 </tex>.  Оба инварианта сохранились, <tex> \Rightarrow </tex> после любого шага алгоритма элементы в очереди неубывают. }} {{Теорема|statement=Алгоритм поиска в ширину в невзвешенном графе находит длины кратчайших путей до всех достижимых вершин.|proof=Допустим, что это не так. Выберем из вершин, для которых кратчайшие пути от <tex> s </tex> найдены некорректно, ту, настоящее расстояние до которой минимально. Пусть это вершина <tex> u </tex>, и она имеет своим предком в дереве обхода в ширину <tex> v </tex>, а предок в кратчайшем пути до <tex> u </tex> — вершина <tex> w </tex>. Так как <tex> w </tex> — предок <tex> u </tex> в кратчайшем пути, то <tex> \rho(s, u) = \rho(s, w) + 1 > \rho(s, w) </tex>, и расстояние до <tex> w </tex> найдено верно, <tex> \rho(s, w) = d[w] </tex>. Значит, <tex> \rho(s, u) = d[w] + 1 </tex>. Так как <tex> v </tex> — предок <tex> u </tex> в дереве обхода в ширину, то <tex> d[u] = d[v] + 1 </tex>. Расстояние до <tex> u </tex> найдено некорректно, поэтому <tex> \rho(s, u) < d[u] </tex>. Подставляя сюда два последних равенства, получаем <tex> d[w] + 1 < d[v] + 1 </tex>, то есть, <tex> d[w] < d[v] </tex>. Из ранее доказанной леммы следует, что в этом случае вершина <tex> w </tex> попала в очередь и была обработана раньше, чем <tex> v </tex>. Но она соединена с <tex> u </tex>, значит, <tex> v </tex> не может быть предком <tex> u </tex> в дереве обхода в ширину, мы пришли к противоречию, следовательно, найденные расстояния до всех вершин являются кратчайшими.}} == Дерево обхода в ширину ==  Поиск в ширину также может построить [[Дерево, эквивалентные определения|дерево]] поиска в ширину. Изначально оно состоит из одного корня <tex> s </tex>. Когда мы добавляем непосещенную вершину в очередь, то добавляем ее и ребро, по которому мы до нее дошли, в дерево. Поскольку каждая вершина может быть посещена не более одного раза, она имеет не более одного родителя. После окончания работы алгоритма для каждой достижимой из <tex> s </tex> вершины <tex> t </tex> путь в дереве поиска в ширину соответствует кратчайшему пути от <tex> s </tex> до <tex> t </tex> в <tex> G </tex>. == Реализация == Предложенная ниже функция возвращает кратчайшее расстояние между двумя вершинами.*<tex> \mathtt{source} </tex> — исходная вершина*<tex> \mathtt{destination} </tex> — конечная вершина*<tex> \mathtt{G} </tex> — граф, состоящий из списка вершин <tex> \mathtt{V} </tex> и списка смежности <tex> \mathtt{E} </tex>. Вершины нумеруются целыми числами.*<tex> \mathtt{Q} </tex> — очередь.*В поле <tex> \mathtt{d[u]} </tex> хранится расстояние от <tex> \mathtt{source} </tex> до <tex> \mathtt{u} </tex>.  '''int''' '''BFS'''(G: (V, E), source: '''int''', destination: '''int'''): d = '''int'''[|V|] '''fill'''(d, <tex> \infty </tex>) d[source] = 0 Q = <tex> \varnothing </tex> Q.push(source) '''while''' Q <tex> \ne \varnothing </tex> u = Q.pop() '''for''' v: (u, v) '''in''' E '''if''' d[v] == <tex> \infty </tex> d[v] = d[u] + 1 Q.push(v) '''return''' d[destination] Если требуется найти расстояние лишь между двумя вершинами, из функции можно выйти, как только будет установлено значение <tex> \mathtt{d[destination]} </tex>.Еще одна оптимизация может быть проведена при помощи метода [[Meet-in-the-middle#Задача о нахождении кратчайшего расстояния между двумя вершинами в графе|meet-in-the-middle]]. == Литература Вариации алгоритма ===== 0-1 BFS ===Пусть в графе разрешены ребра веса <tex> 0 </tex> и <tex> 1 </tex>, необходимо найти кратчайший путь между двумя вершинами. Для решения данной задачи модифицируем приведенный выше алгоритм следующим образом:  Вместо очереди будем использовать [[Персистентный_дек|дек]] (или можно даже steque). Если рассматриваемое ее ребро имеет вес <tex> 0 </tex>, то будем добавлять вершину в начало, а иначе в конец. После этого добавления, дополнительный введенный инвариант в доказательстве [[#Корректность | расположения элементов в деке в порядке неубывания]] продолжает выполняться, поэтому порядок в деке сохраняется. И, соответственно, релаксируем расстояние до всех смежных вершин и, при успешной релаксации, добавляем их в дек.  Таким образом, в начале дека всегда будет вершина, расстояние до которой меньше либо равно расстоянию до остальных вершин дека, и инвариант [[#Корректность | расположения элементов в деке в порядке неубывания]] сохраняется. Значит, алгоритм корректен на том же основании, что и обычный BFS. Очевидно, что каждая вершина войдет в дек не более двух раз, значит, асимптотика у данного алгоритма та же, что и у обычного BFS. === 1-k BFS ===Пусть в графе разрешены ребра целочисленного веса из отрезка <tex>1 \ldots k</tex>, необходимо найти кратчайший путь между двумя вершинами. Представим ребро <tex>uv</tex> веса <tex>m</tex> как последовательность ребер <tex>uu_1u_2 \ldots u_{m - 1}v</tex> (где <tex>u_1 \ldots u_{m - 1}</tex> — новые вершины). Применим данную операцию ко всем ребрам графа <tex> G </tex>. Получим граф, состоящий (в худшем случае) из <tex>k|E|</tex> ребер и <tex>|V| + (k - 1)|E|</tex> вершин. Для нахождения кратчайшего пути следует запустить BFS на новом графе. Данный алгоритм будет иметь асимптотику <tex> O(|V| + k|E|) </tex>. == См. также == * [[Обход в глубину, цвета вершин]]* [[Алгоритм Дейкстры]]* [[Теория графов]] == Источники информации == *Томас Х. Кормен и др, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 20062007. — Сс. 1296459. — ISBN 05-8489-0857-4* [http://e-maxx.ru/algo/bfs MAXimal :: algo :: Поиск в ширину]* [[wikipedia:en:Breadth-first_search| Wikipedia {{---}} Breadth-first search]]* [[wikipedia:ru:Поиск_в_ширину| Wikipedia {{---07}} Поиск в ширину]]* [http://rain.ifmo.ru/cat/view.php/vis/graph-013151general/bfs-12002 Визуализатор алгоритма]  [[Категория: Алгоритмы и структуры данных]][[Категория: Кратчайшие пути в графах]]