Поиск в ширину (BFS): различия между версиями

[непроверенная версия]

Версия от 23:32, 10 июня 2015

Свойства и структура алгоритмов

Алгоритм поиска в ширину (англ. Breadth-First Search, BFS) позволяет вычислить кратчайшие расстояния (в терминах количества рёбер) от выделенной вершины ориентированного графа до всех остальных вершин, и/или построить корневое направленное дерево, расстояния в котором совпадают с расстояниями в исходном графе. Алгоритм решает задачу поиска кратчайшего пути на графе в случае одинаковых весов рёбер. Впервые алгоритм поиска в ширину описан в работах Мура^[1] и Ли^[2].

Общее описание алгоритма

Математическое описание

Вычислительное ядро алгоритма

Макроструктура алгоритма

Описание схемы реализации последовательного алгоритма

Последовательная сложность алгоритма

Информационный граф

Описание ресурса параллелизма алгоритма

Описание входных и выходных данных

Свойства алгоритма

Программная реализация алгоритмов

Особенности реализации последовательного алгоритма

Описание локальности данных и вычислений

Возможные способы и особенности реализации параллельного алгоритма

Масштабируемость алгоритма и его реализации

Динамические характеристики и эффективность реализации алгоритма

Выводы для классов архитектур

Существующие реализации алгоритма

Распределённый алгоритм поиска вширь является вычислительным ядром бенчмарка Graph500.
Boost Graph Library (функции breadth_first_search, breadth_first_visit).

Литература

↑ Moore, Edward F. “The Shortest Path Through a Maze,” 285–92, 1959.
↑ Lee, C Y. “An Algorithm for Path Connections and Its Applications.” IEEE Transactions on Electronic Computers 10, no. 3 (September 1961): 346–65. doi:10.1109/TEC.1961.5219222.

[1] Moore, Edward F. “The Shortest Path Through a Maze,” 285–92, 1959.

[2] Lee, C Y. “An Algorithm for Path Connections and Its Applications.” IEEE Transactions on Electronic Computers 10, no. 3 (September 1961): 346–65. doi:10.1109/TEC.1961.5219222.

[1]

[2]

@@ Строка 22: / Строка 22: @@
 === Существующие реализации алгоритма ===
+* Распределённый алгоритм поиска вширь является вычислительным ядром бенчмарка [http://www.graph500.org Graph500].
 * [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>).