97
правок
Изменения
добавлены примеры задач
'''Обход в ширину''' (Поиск в ширину, англ. ''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> t \in V </tex> считать длину этого пути, равную <tex> d[t] </tex>. Можно считать, что для непосещенных вершин эта длина бесконечно велика. Тогда на каждом шаге длина пути до <tex> t </tex> равна <tex> \rho(s, t) </tex>, если <tex> t </tex> посещена и <tex> \infty </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\limits_{v \in V} deg\ v = 2|E| </tex>, то время, используемое на работу с ребрами, составляет <tex> O(|E|) </tex>. Поэтому общее время работы алгоритма поиска в ширину — <tex> O(|V| + |E|) </tex>.
{{Утверждение
}}
Предложенная ниже функция возвращает расстояние между вершинами source и destination. E - список ребер, Q - очередь. Множество <tex> X </tex> не хранится, вместо него используются расстояния в дереве обхода в ширину. Заметим, что расстояние от вершины source до вершины u, хранится в поле d[u].
Q.push(v)
'''return''' d[destination]
== Примеры задач ==
=== 0-1 BFS ===
Пусть в графе разрешены ребра веса 0 и 1, необходимо найти кратчайший путь между двумя вершинами. Для решения данной задачи модифицируем приведенный выше алгоритм следующим образом: вместо очереди будем использовать [[Персистентный_дек|дек]], а вместо добавления вершины в конец будем добавлять вершину в начало, если рассматриваемое ее ребро имеет вес 0, а иначе в конец. Соответственно релаксируем расстояние до вершины. Таким образом, в начале дека всегда будет вершина, расстояние до которой меньше либо равно расстоянию до остальных вершин дека, и инвариант [[#Корректность | расположения элементов в деке в порядке неубывания]] сохраняется. Значит, алгоритм корректен на том же основании, что и обычный BFS. Очевидно, что каждая вершина войдет в дек не более двух раз, значит, асимптотика у данного алгоритма та же, что и у обычного BFS.
=== 1-k BFS ===
Пусть в графе разрешены ребра веса <tex>1..k</tex>, необходимо найти кратчайший путь между двумя вершинами. Представим ребро <tex>uv</tex> веса <tex>m</tex> как последовательность ребер <tex>uu_1u_2..u_{m - 1}v</tex> (где <tex>u_1..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)|E|) </tex>.
== Источники информации ==
