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

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

Версия от 16:24, 11 июня 2015

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

↑ 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]

@@ Строка 24: / Строка 24: @@
 * Распределённый алгоритм поиска вширь является вычислительным ядром бенчмарка [http://www.graph500.org Graph500].
-* C++: [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>).
+* C++: [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/libs/graph/doc/breadth_first_visit.html breadth_first_visit]</code>).
-* C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library] (функция [http://www.boost.org/libs/graph_parallel/doc/html/breadth_first_search.html breadth_first_search]).
+* C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/breadth_first_search.html breadth_first_search]</code>).
 * Java: [http://webgraph.di.unimi.it WebGraph] (класс <code>[http://webgraph.di.unimi.it/docs/it/unimi/dsi/webgraph/algo/ParallelBreadthFirstVisit.html ParallelBreadthFirstVisit]</code>), многопоточная реализация.