1632
правки
Изменения
м
ш-
rollbackEdits.php mass rollback
Для алгоритма нам потребуются [[Очередь|очередь]] и множество посещенных вершин <tex> was </tex>, которые изначально содержат одну вершину <tex> s </tex>. На каждом шагу алгоритм берет из начала очереди вершину <tex> v </tex> и добавляет все непосещенные смежные с <tex> v </tex> вершины в <tex> was </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> 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> x </tex> и, после них, <tex> b + r </tex> вершин с расстоянием <tex> x + 1 </tex>.
Оба инварианта сохранились, <tex> \Rightarrow </tex> после любого шага алгоритма элементы в очереди неубывают.
