Изменения

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

Пусть задан невзвешенный граф <tex>G = (V, E)</tex>, в котором выделена исходная вершина <tex>s</tex>. Для алгоритма нам потребуются очередь, которая сначала содержит только <tex> s </tex>, и множество посещенных вершин <tex> X </tex>, которое изначально тоже содержит только <tex> s </tex>. На каждом шаге алгоритм вынимает из начала очереди вершину, рассматривает все исходящие из нее ребра и добавляет все связанные с ней непосещенные вершины в <tex> X </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} deпdeg\ v = 2|E| </tex>, то время, используемое на работу с ребрами, составляет <tex> O(|E|) </tex>. Поэтому общее время работы алгоритма поиска в ширину — <tex> O(|V | + |E|) </tex>.

В алгоритме поиска в ширину очередь всегда содержит сначала вершины некоторое количество вершин с расстоянием k, а потом, возможно, вершины некоторое количество вершин с расстоянием k + 1(возможно, нулевое).