Изменения

{{В разработке}}'''Обход в ширину''' ('''Поиск в ширину, англ. ''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_{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> вершин с расстоянием 0<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> 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> 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> s{w_1}{w_2}{\ldots}wu v </tex> - этот кратчайший путь. Понятно, что — предок <tex> s{w_1}{w_2}{\ldots}w u </tex> - кратчайший путь до <tex> w </tex> (если бы он не был кратчайшимв дереве обхода в ширину, то можно было бы заменить его на кратчайший в пути до <tex> u </tex>, значит, путь до <tex> u </tex> — тоже не кратчайший). Вес каждого ребра равен 1, значит, <tex> d[u] > \rho(s, u) = d[wv] + 1 </tex>, и <tex> d[w] < d[u] </tex>. Неравенство <tex> d[v] < d[u] </tex> следует из того, что <tex> v </tex> — предок <tex> u </tex> в дереве поиска в ширину. Итак, расстояние до вершин <tex> v </tex> и <tex> w </tex> найдено корректно.

Путь через Расстояние до <tex> w 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 \emptyset </tex> 3 Q.push(s) 4 '''while''' Q <tex> \ne \emptyset </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)

Таким образом, в начале дека всегда будет вершина, расстояние до которой меньше либо равно расстоянию до остальных вершин дека, и инвариант [http://e-maxx[#Корректность | расположения элементов в деке в порядке неубывания]] сохраняется.ru/algo/bfs Поиск Значит, алгоритм корректен на том же основании, что и обычный BFS. Очевидно, что каждая вершина войдет в ширину на e-maxxдек не более двух раз, значит, асимптотика у данного алгоритма та же, что и у обычного BFS.ru]

[http:=== 1-k BFS ===Пусть в графе разрешены ребра целочисленного веса из отрезка <tex>1 \ldots k</tex>, необходимо найти кратчайший путь между двумя вершинами. Представим ребро <tex>uv</tex> веса <tex>m</rutex> как последовательность ребер <tex>uu_1u_2 \ldots u_{m - 1}v</tex> (где <tex>u_1 \ldots u_{m - 1}</tex> — новые вершины).wikipediaПрименим данную операцию ко всем ребрам графа <tex> G </tex>.orgПолучим граф, состоящий (в худшем случае) из <tex>k|E|</wikitex> ребер и <tex>|V| + (k - 1)|E|</Поиск_в_ширину Поиск в ширину в Википедии]tex> вершин. Для нахождения кратчайшего пути следует запустить BFS на новом графе. Данный алгоритм будет иметь асимптотику <tex> O(|V| + k|E|) </tex>.

== См. также == * [http://rain.ifmo.ru/cat/view.php/vis/graph-general/bfs-2002 Визуализатор алгоритма[Обход в глубину, цвета вершин]]* [[Алгоритм Дейкстры]]* [[Теория графов]]

== Литература Источники информации ==

*Томас Х. Кормен и др, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = 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 Визуализатор алгоритма]