Поиск в ширину (BFS)

Get Perf.Data

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

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

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

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

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

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

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

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

Пусть задан граф [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]d(u)=0[/math], до остальных вершин [math]d(v) = \infty, \forall v \neq u [/math]. Так же в начале работы алгоритм инициализируются множество [math]F = \{u\}[/math].

Далее на каждом шаге алгоритм строится множество вершин [math]P = {w} [/math], таких, что для [math]\forall v \in F \exists (v, w) \in E | d(w) = \infty [/math], при том обновляются расстояния [math]d(w)=d(v)+1[/math] для [math]\forall w \in P [/math]. Затем производится переход на следующий шаг до тех пор, пока [math]P \neq \emptyset[/math], при том в начале каждого шага множество F заменяется на P.

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

Вычислительным ядром алгоритма является обход вершин, смежной к выбранной вершине [math]v[/math] с последующем добавлением еще не посещенных вершин в множество [math]P[/math]. Данная операция выполняться на каждом шаге для каждой вершины [math]v \in F[/math].

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

Алгоритм последовательно уточняет значения функции [math]d(v)[/math].

Структуру можно описать следующим образом:

1. Инициализация: всем вершинам присваивается предполагаемое расстояние [math]d(v)=\infty[/math], кроме вершины-источника, для которой [math]d(u)=0[/math] .

2. Помещение вершины источника [math]v[/math] в множество "передовых" вершин [math]F[/math].

3. Обход вершин множества [math]F[/math].

а) Инициализация множества [math]P=\emptyset[/math].

б) Для каждой вершины [math]v \in F[/math] обход всех вершин [math]w | \exists (v, w)[/math] (смежных с ней), c помещением в множество [math]P[/math] таких вершин [math]w | d(w)=\infty[/math].

в) Замена множества [math]F[/math] на [math]P[/math] и переход на шаг 3 в случае, если множество [math]F \neq \emptyset[/math].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Распределённый алгоритм поиска вширь является вычислительным ядром бенчмарка 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).

3 Литература

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