Поиск в ширину (BFS): различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [непроверенная версия] |
Daryin (обсуждение | вклад) Общее описание алгоритма |
Daryin (обсуждение | вклад) |
||
| Строка 21: | Строка 21: | ||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
=== Существующие реализации алгоритма === | === Существующие реализации алгоритма === | ||
* [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функции <code>[http://www.boost.org/libs/graph/doc/breadth_first_search.html breadth_first_search]</code>, <code>[http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/breadth_first_visit.html breadth_first_visit]</code>). | |||
== Литература == | == Литература == | ||
<references /> | <references /> | ||
Версия от 21:29, 10 июня 2015
Свойства и структура алгоритмов
Алгоритм поиска в ширину (англ. Breadth-First Search, BFS) позволяет вычислить кратчайшие расстояния (в терминах количества рёбер) от выделенной вершины ориентированного графа до всех остальных вершин, и/или построить корневое направленное дерево, расстояния в котором совпадают с расстояниями в исходном графе. Алгоритм решает задачу поиска кратчайшего пути на графе в случае одинаковых весов рёбер. Впервые алгоритм поиска в ширину описан в работах Мура[1] и Ли[2].