Изменения

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

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

Пусть задан невзвешенный ориентированный граф <tex> G = (V, E) </tex>, в котором выделена исходная вершина <tex>s</tex>. Для алгоритма нам потребуются очередьТребуется найти длину кратчайшего пути (если таковой имеется) от одной заданной вершины до другой. Частным случаем указанного графа является невзвешенный неориентированный граф, которая сначала содержит только <tex> s </tex>, и множество посещенных вершин <tex> X </tex>, которое изначально тоже содержит только <tex> s </tex>т.е. На каждом шаге алгоритм вынимает из начала очереди вершинуграф, рассматривает все исходящие из нее в котором для каждого ребра и добавляет все связанные с ней непосещенные найдется обратное, соединяющее те же вершины в <tex> X </tex> и в конец очереди. Если очередь пуста, то алгоритм завершает работудругом направлении.

Поиск в ширину также может построить дерево поиска в ширину. Изначально оно состоит из одного корня Для алгоритма нам потребуются [[Очередь|очередь]] и множество посещенных вершин <tex> s was </tex>. Когда мы добавляем непосещенную , которые изначально содержат одну вершину в очередь, то добавляем ее и ребро, по которому мы до нее дошли, в дерево. Поскольку каждая вершина может быть посещена не более одного раза, она имеет не более одного родителя. После окончания работы алгоритма для каждой достижимой из <tex> s </tex> вершины . На каждом шагу алгоритм берет из начала очереди вершину <tex> t v </tex> путь в дереве поиска в ширину соответствует кратчайшему пути от и добавляет все непосещенные смежные с <tex> s v </tex> до вершины в <tex> t was </tex> и в <tex> G </tex>конец очереди. Если очередь пуста, то алгоритм завершает работу.

Оценим время работы для входного графа <tex>G = (V, E)</tex>. В очередь добавляются только непосещенные вершины, поэтому каждая вершина посещается не более одного раза. Операции внесения в очередь и удаления из нее требуют <tex> O(1) </tex> времени, так что общее время работы с очередью составляет <tex> O(|V|) </tex> операций. Для каждой вершины <tex> v </tex> рассматривается не более <tex> deg\ v </tex> ребер, инцидентных ей. Так как <tex> \sum_{v \in V} deg\ v = 2|E| </tex>, то время, используемое на работу с ребрами, составляет <tex> O(|E|) </tex>. Поэтому общее время работы алгоритма поиска в ширину — <tex> O(|V| + |E|) </tex>. === Корректность ===

В алгоритме очереди поиска в ширину очередь всегда содержит сначала некоторое количество расстояние вершин с расстоянием k, а потом некоторое количество вершин с расстоянием k + 1(возможно, нулевое)до <tex>s</tex> монотонно неубывает.

Докажем это утверждение индукцией по шагам алгоритмачислу выполненных алгоритмом шагов. Введем дополнительный инвариант: у любых двух вершин из очереди, расстояние до <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> s v </tex> , с расстоянием 0<tex> x </tex>. Пусть у v есть <tex>r </tex> непосещенных смежных вершин. Тогда, после их добавления, утверждение вернов очереди находится <tex> a </tex> вершин с расстоянием <tex> x </tex> и, после них, <tex> b + r </tex> вершин с расстоянием <tex> x + 1 </tex>.

Переход: пусть после Оба инварианта сохранились, <tex> l \Rightarrow </tex>-ого после любого шага алгоритма очередь содержит <tex> p </tex> вершин с расстоянием <tex> k </tex> и <tex> q </tex> вершин с расстоянием <tex> k + 1 </tex>. Тогда на <tex> l+1 </tex>-ом шаге мы извлечем из элементы в очереди одну вершину и добавим в нее все непосещенные(<tex> r </tex> вершин), связанные с ней; расстояние до них, очевидно, будет равно <tex> k + 1 </tex>. У нас останется <tex> p - 1 </tex>(возможно, 0) вершин с расстоянием <tex> k </tex> и <tex> q + r </tex> вершин с расстоянием k + 1, что соответствует нашему инвариантунеубывают.

Алгоритм поиска в ширину в невзвешенном графе находит оптимальные расстояния длины кратчайших путей до всех достижимых вершин.

Допустим, что это не так. Выберем из вершин, для которых найдено неоптимальное расстояние кратчайшие пути от <tex> s </tex> найдены некорректно, ту, которая находится на минимальном расстояниинастоящее расстояние до которой минимально. Пусть это вершина <tex> u </tex>, и она имеет своим предком в дереве обхода в ширину <tex> v </tex>, а предкок предок в оптимальном кратчайшем пути до <tex> v u </tex> — вершина <tex> w </tex>. Расстояние до вершин  Так как <tex> w </tex> — предок <tex> u </tex> в кратчайшем пути, то <tex> v \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> G = (VЕсли требуется найти расстояние лишь между двумя вершинами, E) </tex> - входной графиз функции можно выйти, как только будет установлено значение <tex> s \mathtt{d[destination]} </tex> .Еще одна оптимизация может быть проведена при помощи метода [[Meet- выделенная вершина, Q in-the- очередь. Множество <tex> X </tex> не хранится, вместо него использются middle#Задача о нахождении кратчайшего расстояния между двумя вершинами в дереве обхода в ширину; расстояние от <tex>s</tex> до вершины <tex>u</tex>, вычисляемое алгоритмом, хранится в поле <tex>d[uграфе|meet-in-the-middle]]</tex>.

'''== Вариации алгоритма ===== 0-1 BFS'''(<tex>G</tex>, <tex>s</tex>)=== 1 d[s] Пусть в графе разрешены ребра веса <tex> \leftarrow </tex> 0 2 Q <tex> \leftarrow \varnothing </tex> 3 Q.push(s) 4 '''while''' Q <tex> \ne \varnothing </tex> 5 '''do''' u и <tex> \leftarrow 1 </tex> Q, необходимо найти кратчайший путь между двумя вершинами.pop 6 '''for''' vДля решения данной задачи модифицируем приведенный выше алгоритм следующим образом: uv <tex> \in </tex> E 7 '''do''' '''if''' d[v] = <tex> \infty </tex> 8 '''then''' d[v] <tex> \leftarrow </tex> d[u] + 1 9 Q.push(v)

*Томас Х. Кормен Таким образом, в начале дека всегда будет вершина, расстояние до которой меньше либо равно расстоянию до остальных вершин дека, и дринвариант [[#Корректность | расположения элементов в деке в порядке неубывания]] сохраняется. Алгоритмы: построение Значит, алгоритм корректен на том же основании, что и анализ = INTRODUCTION TO ALGORITHMSобычный BFS. — 2-е изд. — М.: «Вильямс»Очевидно, что каждая вершина войдет в дек не более двух раз, значит, асимптотика у данного алгоритма та же, 2006. — С. 1296что и у обычного BFS. — ISBN 0-07-013151-1

== Ссылки =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>.

== См. также == * [[http://e-maxx.ru/algo/bfs Поиск Обход в ширину на e-maxx.ruглубину, цвета вершин]]* [[Алгоритм Дейкстры]]* [[Теория графов]]

* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4* [http://e-maxx.ru/algo/bfs MAXimal :: algo :: Поиск в ширину]* [[wikipedia:en:Breadth-first_search| Wikipedia {{---}} Breadth-first search]]* [[wikipedia:ru:Поиск_в_ширину| Wikipedia {{---}} Поиск в ширину]]* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/bfs-2002 Визуализатор алгоритма]