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

Алгоритм 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) позволяет вычислить кратчайшие расстояния (в терминах количества рёбер) от выделенной вершины ориентированного графа до всех остальных вершин, и/или построить корневое направленное дерево, расстояния в котором совпадают с расстояниями в исходном графе. Кроме того, поиск в ширину позволяет решать задачу проверки достижимости (существуют ли пути между вершиной источником и остальными вершинами графа). Впервые алгоритм поиска в ширину описан в работах Мура и Ли.

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

В последовательном случае алгоритм имеет алгоритмическую сложность [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] до всех остальных вершин графа описанным далее образом.

В начале работы алгоритма расстояние до вершины-источника [math]\displaystyle{ d(u)=0 }[/math], до остальных вершин [math]\displaystyle{ d(v) = inf, \forall v \neq u }[/math]. Так же в начале работы алгоритм инициализируются множество [math]\displaystyle{ F = \{u\} }[/math].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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