Изменения

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

Также можно для каждой вершины Для алгоритма нам потребуются [[Очередь|очередь]] и множество посещенных вершин <tex> t \in V was </tex> считать длину этого пути, равную которые изначально содержат одну вершину <tex> d[t] s </tex>. Можно считать, что для непосещенных вершин эта длина бесконечно велика. Тогда на На каждом шаге длина пути до шагу алгоритм берет из начала очереди вершину <tex> t v </tex> равна и добавляет все непосещенные смежные с <tex> \rho(s, t) v </tex>, если вершины в <tex> t was </tex> посещена и <tex> \infty </tex> в противном случаеконец очереди. Отсюда следует, что если на каждом шаге обновлять длины путейЕсли очередь пуста, то информация о множестве <tex> X </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> вершин с расстоянием 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> 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> \mathtt{source } </tex> — исходная вершина*<tex> \mathtt{destination} </tex> — конечная вершина*<tex> \mathtt{G} </tex> — граф, состоящий из списка вершин <tex> \mathtt{V} </tex> и destinationсписка смежности <tex> \mathtt{E} </tex>. Вершины нумеруются целыми числами. E - список ребер, *<tex> \mathtt{Q - } </tex> — очередь. Множество *В поле <tex> X \mathtt{d[u]} </tex> не хранится, вместо него используются расстояния в дереве обхода в ширину. Заметим, что расстояние от вершины <tex> \mathtt{source } </tex> до вершины <tex> \mathtt{u, хранится в поле d[u]} </tex>.

'''int''' '''BFS'''(G: (V, E), source: '''list'''<'''int''', destination: '''int'''>, source): d = '''int''', destination: [|V|] '''intfill''') (d.fill(, <tex> \infty </tex>)

q u = Q.pop() '''for''' <qv: (u, v> ) '''in''' E

d[v] = d[qu] + 1

Если требуется найти расстояние лишь между двумя вершинами, из функции можно выйти, как только будет установлено значение <tex> \mathtt{d[destination]} </tex>.Еще одна оптимизация может быть проведена при помощи метода [[Meet-in-the-middle#Задача о нахождении кратчайшего расстояния между двумя вершинами в графе|meet-in-the-middle]]. == Примеры задач Вариации алгоритма ==

Пусть в графе разрешены ребра веса <tex> 0 </tex> и <tex> 1</tex>, необходимо найти кратчайший путь между двумя вершинами. Для решения данной задачи модифицируем приведенный выше алгоритм следующим образом: вместо  Вместо очереди будем использовать [[Персистентный_дек|дек]](или можно даже steque). Если рассматриваемое ее ребро имеет вес <tex> 0 </tex>, а вместо добавления вершины в конец то будем добавлять вершину в начало, если рассматриваемое ее ребро имеет вес 0, а иначе в конец. Соответственно После этого добавления, дополнительный введенный инвариант в доказательстве [[#Корректность | расположения элементов в деке в порядке неубывания]] продолжает выполняться, поэтому порядок в деке сохраняется. И, соответственно, релаксируем расстояние до вершинывсех смежных вершин и, при успешной релаксации, добавляем их в дек.  Таким образом, в начале дека всегда будет вершина, расстояние до которой меньше либо равно расстоянию до остальных вершин дека, и инвариант [[#Корректность | расположения элементов в деке в порядке неубывания]] сохраняется. Значит, алгоритм корректен на том же основании, что и обычный BFS. Очевидно, что каждая вершина войдет в дек не более двух раз, значит, асимптотика у данного алгоритма та же, что и у обычного 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(V, E)</tex>. Получим граф, состоящий (в худшем случае) из <tex>k|E|</tex> ребер и <tex>|V| + (k - 1)|E|</tex> вершин. Для нахождения кратчайшего пути следует запустить BFS на новом графе. Асимптотикой данного алгоритма является Данный алгоритм будет иметь асимптотику <tex> O(|V| + (2k - 1)k|E|) </tex>. == См. также == * [[Обход в глубину, цвета вершин]]* [[Алгоритм Дейкстры]]* [[Теория графов]]