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

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

Версия от 18:42, 7 августа 2017

Алгоритм DCSC поиска компонент сильной связности
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ O(n + m) }[/math]
Объём входных данных	[math]\displaystyle{ O(m + n) }[/math]
Объём выходных данных	[math]\displaystyle{ O(n) }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]\displaystyle{ N/A, max O(V) }[/math]
Ширина ярусно-параллельной формы	[math]\displaystyle{ N/A, max O(E) }[/math]

Основные авторы описания: И.В.Афанасьев

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

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

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

Алгоритм основан на обходе вершин графа "по слоям". На каждом шаге есть множество "передовых" вершин, для смежных к которым производится проверка, относятся ли они к еще не посещенным. Все еще не посещенные вершины добавляются в новое множество "передовых" вершин, обрабатываемых на следующем шаге. Изначально в множество "передовых" вершин входит только вершина-источник, от которой и начинается обход.

В последовательном случае алгоритм имеет алгоритмическую сложность [math]\displaystyle{ O(n + m) }[/math], где [math]\displaystyle{ n }[/math] - число вершин в графе, [math]\displaystyle{ m }[/math] - число ребер в графе.

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

Пусть задан граф [math]\displaystyle{ G = (V, E) }[/math] без весов, и с выделенной вершиной-источником [math]\displaystyle{ u }[/math]. Путем [math]\displaystyle{ P(u,v) }[/math] между вершинами [math]\displaystyle{ u }[/math] и [math]\displaystyle{ v }[/math] называется множество ребер [math]\displaystyle{ (u, v_1), (v_1, v_2), ... (v_{n-1}, v) }[/math]. Длиной пути [math]\displaystyle{ d(u,v) }[/math] обозначим число ребер в данном пути между вершинами [math]\displaystyle{ u }[/math] и [math]\displaystyle{ v }[/math]. Поиск в ширину находит кратчайшие пути [math]\displaystyle{ d(u,v) }[/math] от вершины [math]\displaystyle{ u }[/math] до всех остальных вершин графа следующим образом:

// TODO

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

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

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

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

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

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

Входные и выходные данные алгоритма

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

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

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

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

Локальность реализации алгоритма

Структура обращений в память и качественная оценка локальности

Количественная оценка локальности

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

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

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

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

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

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

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

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

Литература

↑ Moore, Edward F. “The Shortest Path Through a Maze,” International Symposium on the Theory of Switching, 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,” International Symposium on the Theory of Switching, 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: @@
 === Математическое описание алгоритма ===
-Пусть задан граф <math>G = (V, E)</math> без весов, и с выделенной вершиной-источником <math>u</math>. Путем <math>P(u,v)</math> между вершинами <math>u</math> и <math>v</math> называется множество ребер <math>(u, v_1), (v_1, v_2), ... (v_n-1, v)</math>. Длиной пути <math>d(u,v)</math> обозначим число ребер в данном пути между вершинами <math>u</math> и <math>v</math>. Поиск в ширину находит кратчайшие пути <math>d(u,v)</math> от вершины <math>u</math> до всех остальных вершин графа следующим образом:
+Пусть задан граф <math>G = (V, E)</math> без весов, и с выделенной вершиной-источником <math>u</math>. Путем <math>P(u,v)</math> между вершинами <math>u</math> и <math>v</math> называется множество ребер <math>(u, v_1), (v_1, v_2), ... (v_{n-1}, v)</math>. Длиной пути <math>d(u,v)</math> обозначим число ребер в данном пути между вершинами <math>u</math> и <math>v</math>. Поиск в ширину находит кратчайшие пути <math>d(u,v)</math> от вершины <math>u</math> до всех остальных вершин графа следующим образом:
 // TODO