Изменения

Перейти к: навигация, поиск

Обход в ширину

258 байт добавлено, 21:32, 3 декабря 2014
fixes
== Анализ времени работы ==
Оценим время работы для входного графа <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>.
== Корректность ==
Предложенная ниже функция возвращает кратчайшее расстояние между двумя вершинами.
<ul> <li>*<tex> \mathtt{source} </tex> — исходная вершина</li> <li>*<tex> \mathtt{destination} </tex> — конечная вершина</li> <li>*<tex> \mathtt{G} </tex> — граф, состоящий из списка вершин <tex> \mathtt{V} </tex> и списка смежности <tex> \mathtt{E} </tex>. Вершины нумеруются целыми числами.</li> <li>*<tex> \mathtt{Q} </tex> — очередь.</li> <li>*В поле <tex> \mathtt{d[u]} </tex> хранится расстояние от <tex> \mathtt{source} </tex> до <tex> \mathtt{u} </tex>.</li></ul>
'''int''' '''BFS'''(EG: <(V, E>), source: '''int''', destination: '''int''') d = '''int'''[|V|] d.'''fill'''(d, <tex> \infty </tex>)
d[source] = 0
Q = <tex> \varnothing </tex>
'''for''' vu '''in''' E
'''if''' d[v] == <tex> \infty </tex>
d[v] = d[qu] + 1
Q.push(v)
'''return''' d[destination]
Если требуется найти расстояние лишь между двумя вершинами, из функции можно выйти, как только будет установлено значение <tex> \mathtt{d[destination]} </tex>.
Еще одна оптимизация может быть проведена при помощи метода [[Meet-in-the-middle#Задача о нахождении кратчайшего расстояния между двумя вершинами в графе|meet-in-the-middle]].
== Вариации алгоритма ==
=== 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| + k|E|) </tex>.
== Источники информации ==
97
правок

Навигация