Изменения
Нет описания правки
== Описание алгоритма ==
[[Image: Graph-BFS.gif|thumb|240px|Алгоритм BFS<br>
<font color=#3c9eff>посещенные</font> вершины<br>]]
Пусть задан невзвешенный ориентированный граф <tex> G = (V, E) </tex>, в котором выделена исходная вершина <tex>s</tex>. Требуется найти длину кратчайшего пути (если таковой имеется) от одной заданной вершины до другой. Частным случаем указанного графа является невзвешенный неориентированный граф, т.е. граф, в котором для каждого ребра найдется обратное, соединяющее те же вершины в другом направлении.
== Анализ времени работы ==
Оценим время работы для входного графа <tex>G = (V, E)</tex>, где множество ребер <tex> E </tex> представлено списком смежности. В очередь добавляются только непосещенные вершины, поэтому каждая вершина посещается не более одного раза. Операции внесения в очередь и удаления из нее требуют <tex> O(1) </tex> времени, так что общее время работы с очередью составляет <tex> O(|V|) </tex> операций. Для каждой вершины <tex> v </tex> рассматривается не более <tex> \mathrm{deg}(v) </tex> ребер, инцидентных ей. Так как <tex> \sum\limits_{v \in V} \mathrm{deg}(v) = 2|E| </tex>, то время, используемое на работу с ребрами, составляет <tex> O(|E|) </tex>. Поэтому общее время работы алгоритма поиска в ширину — <tex> O(|V| + |E|) </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> v </tex>, с расстоянием <tex> x </tex>. Пусть у <tex>v</tex> есть <tex>r </tex> непосещенных смежных вершин. Тогда, после их добавления, в очереди находится <tex> a </tex> вершин с расстоянием <tex> 0 x </tex>и, после них, утверждение верно<tex> b + r </tex> вершин с расстоянием <tex> x + 1 </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>.
'''while''' Q <tex> \ne \varnothing </tex>
u = Q.pop()
'''for''' v: (u, v, u) '''in''' E
'''if''' d[v] == <tex> \infty </tex>
d[v] = d[u] + 1
== Вариации алгоритма ==
=== 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>. == См. также == * [[Обход в глубину, цвета вершин]]* [[Алгоритм Дейкстры]]* [[Теория графов]]
== Источники информации ==
