Изменения

'''Обход в ширину''' ('''Поиск в ширину''', '''BFS''', '''Breadth-first search''') — один из простейших алгоритмов обхода графа, являющийся основой для многих важных алгоритмов для работы с графами.

Оценим время работы для входного графа <tex>G = (V, E)</tex>. В очередь добавляются только непосещенные вершины, поэтому каждая вершина посещается не более одного раза. Операции внесения в очередь и удаления из нее требуют <tex> O(1) </tex> времени, так что общее время работы с очередью составляет <tex> O(|V|) </tex> операций. Для каждой вершины <tex> v </tex> рассматривается не более <tex> deg\ v </tex> ребер, инцидентных ей. Так как <tex> \sum_sum\limits_{v \in V} deg\ v = 2|E| </tex>, то время, используемое на работу с ребрами, составляет <tex> O(|E|) </tex>. Поэтому общее время работы алгоритма поиска в ширину — <tex> O(|V| + |E|) </tex>.

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

Путь через Так как <tex> w v </tex> — предок <tex> u </tex> кратчайшийв дереве обхода в ширину, а через то <tex> d[u] = d[v ] + 1 </tex>. Расстояние до <tex> 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> в дереве обхода в ширину, мы пришли к противоречию, следовательно, найденные расстояния до всех вершин являются кратчайшими.