'''Обход в ширину''' ('''Поиск в ширину''', 'англ. ''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> t \in G = (V , E)</tex> считать длину этого пути, равную где множество ребер <tex> d[t] E </tex>представлено списком смежности. Можно считатьВ очередь добавляются только непосещенные вершины, что для непосещенных вершин эта длина бесконечно великапоэтому каждая вершина посещается не более одного раза. Тогда на каждом шаге длина пути до Операции внесения в очередь и удаления из нее требуют <tex> t O(1) </tex> равна времени, так что общее время работы с очередью составляет <tex> \rhoO(s, t|V|) </tex>, если операций. Для каждой вершины <tex> t v </tex> посещена и рассматривается не более <tex> \infty mathrm{deg}(v) </tex> в противном случаеребер, инцидентных ей. Отсюда следуетТак как <tex> \sum\limits_{v \in V} \mathrm{deg}(v) = 2|E| </tex>, то время, что если используемое на каждом шаге обновлять длины путейработу с ребрами, то информация о множестве составляет <tex> O(|E|) </tex>. Поэтому общее время работы алгоритма поиска в ширину — <tex> X O(|V| + |E|) </tex> является избыточной, и его можно не хранить.
=== Анализ времени работы === Оценим время работы для входного графа <tex>G = (V, E)</tex>. В очередь добавляются только непосещенные вершины, поэтому каждая вершина посещается не более одного раза. Операции внесения в очередь и удаления из нее требуют <tex> O(1) </tex> времени, так что общее время работы с очередью составляет <tex> O(|V|) </tex> операций. Для каждой вершины <tex> v </tex> рассматривается не более <tex> deg\ v </tex> ребер, инцидентных ей. Так как <tex> \sum\limits_{v \in V} deg\ v = 2|E| </tex>, то время, используемое на работу с ребрами, составляет <tex> O(|E|) </tex>. Поэтому общее время работы алгоритма поиска в ширину — <tex> O(|V| + |E|) </tex>. === Корректность ===
{{Утверждение
|statement=
В очереди поиска в ширину расстояние вершин до <tex>s</tex> монотонно неубывает.
|proof=
Докажем это утверждение индукцией по числу выполненных алгоритмом шагов.
Введем дополнительный инвариант: у любых двух вершин из очереди, расстояние до <tex> s </tex> отличается не более чем на <tex> 1 </tex>. '''База''': изначально очередь содержит только одну вершину <tex> s </tex> с расстоянием 0, утверждение верно.
'''Переход''': пусть после <tex> l i-й </tex>-ого шага алгоритма очередь содержит итерации в очереди <tex> p a + 1 </tex> вершин с расстоянием <tex> k x </tex> и <tex> q b </tex> вершин с расстоянием <tex> k x + 1 </tex>. Тогда на Рассмотрим <tex> l+1 i-ю </tex>-ом шаге мы извлечем из итерацию. Из очереди одну достаем вершину и добавим в нее все непосещенные(<tex> r v </tex> вершин), связанные с ней; расстояние до них, очевидно, будет равно расстоянием <tex> k + 1 x </tex>. У нас останется Пусть у <tex>v</tex> p - 1 есть <tex>r </tex> (возможнонепосещенных смежных вершин. Тогда, 0) после их добавления, в очереди находится <tex> a </tex> вершин с расстоянием <tex> k x </tex> и , после них, <tex> q b + r </tex> вершин с расстоянием k <tex> x + 1</tex>. Оба инварианта сохранились, что соответствует нашему инварианту<tex> \Rightarrow </tex> после любого шага алгоритма элементы в очереди неубывают.
}}
Допустим, что это не так. Выберем из вершин, для которых кратчайшие пути от <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> G = (V, E) s </tex> - входной граф. Когда мы добавляем непосещенную вершину в очередь, то добавляем ее и ребро, по которому мы до нее дошли, в дерево. Поскольку каждая вершина может быть посещена не более одного раза, она имеет не более одного родителя. После окончания работы алгоритма для каждой достижимой из <tex> s </tex> - выделенная вершина, Q - очередь. Множество вершины <tex> X t </tex> не хранится, вместо него используются расстояния путь в дереве обхода поиска в ширину; расстояние соответствует кратчайшему пути от <tex>s</tex> до вершины <tex>ut </tex>, вычисляемое алгоритмом, хранится в поле <tex>d[u]G </tex>.
'''BFS'''(<tex>G</tex>, <tex>s</tex>) 1 d[s] <tex> \leftarrow </tex> 0 2 Q <tex> \leftarrow \emptyset </tex> 3 Q.push(s) 4 '''while''' Q <tex> \ne \emptyset </tex> 5 '''do''' u <tex> \leftarrow </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)= Реализация ==
== Ссылки ==Предложенная ниже функция возвращает кратчайшее расстояние между двумя вершинами.*<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[http:source] = 0 Q = <tex> \varnothing </tex> Q.push(source) '''while''' Q <tex> \ne \varnothing </e-maxxtex> u = Q.rupop() '''for''' v: (u, v) '''in''' E '''if''' d[v] == <tex> \infty </algotex> d[v] = d[u] + 1 Q.push(v) '''return''' d[destination] Если требуется найти расстояние лишь между двумя вершинами, из функции можно выйти, как только будет установлено значение <tex> \mathtt{d[destination]} </bfs Поиск tex>.Еще одна оптимизация может быть проведена при помощи метода [[Meet-in-the-middle#Задача о нахождении кратчайшего расстояния между двумя вершинами в ширину на eграфе|meet-in-the-maxxmiddle]].ru]* [http:== Вариации алгоритма ===== 0-1 BFS ===Пусть в графе разрешены ребра веса <tex> 0 </tex> и <tex> 1 </rutex>, необходимо найти кратчайший путь между двумя вершинами.wikipediaДля решения данной задачи модифицируем приведенный выше алгоритм следующим образом: Вместо очереди будем использовать [[Персистентный_дек|дек]] (или можно даже steque).orgЕсли рассматриваемое ее ребро имеет вес <tex> 0 </wiki/Поиск_в_ширину Поиск tex>, то будем добавлять вершину в начало, а иначе в конец. После этого добавления, дополнительный введенный инвариант в доказательстве [[#Корректность | расположения элементов в ширину деке в Википедиипорядке неубывания]]продолжает выполняться, поэтому порядок в деке сохраняется. И, соответственно, релаксируем расстояние до всех смежных вершин и, при успешной релаксации, добавляем их в дек. * Таким образом, в начале дека всегда будет вершина, расстояние до которой меньше либо равно расстоянию до остальных вершин дека, и инвариант [[http:#Корректность | расположения элементов в деке в порядке неубывания]] сохраняется. Значит, алгоритм корректен на том же основании, что и обычный BFS. Очевидно, что каждая вершина войдет в дек не более двух раз, значит, асимптотика у данного алгоритма та же, что и у обычного BFS. === 1-k BFS ===Пусть в графе разрешены ребра целочисленного веса из отрезка <tex>1 \ldots k</tex>, необходимо найти кратчайший путь между двумя вершинами. Представим ребро <tex>uv</tex> веса <tex>m</rain.ifmo.rutex> как последовательность ребер <tex>uu_1u_2 \ldots u_{m - 1}v</cattex> (где <tex>u_1 \ldots u_{m - 1}</viewtex> — новые вершины).phpПрименим данную операцию ко всем ребрам графа <tex> G </vistex>. Получим граф, состоящий (в худшем случае) из <tex>k|E|</graphtex> ребер и <tex>|V| + (k -general1)|E|</bfs-2002 Визуализатор алгоритмаtex> вершин. Для нахождения кратчайшего пути следует запустить BFS на новом графе. Данный алгоритм будет иметь асимптотику <tex> O(|V| + k|E|) </tex>. == См. также == * [[Обход в глубину, цвета вершин]]* [[Алгоритм Дейкстры]]* [[Теория графов]]
== Литература Источники информации ==
*Томас Х. Кормен и др, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 20062007. — Сс. 1296459. — ISBN 05-8489-0857-4* [http://e-07maxx.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-013151general/bfs-12002 Визуализатор алгоритма]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах]]
