Поиск в ширину (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 Схема реализации последовательного алгоритма

Простейшая версия алгоритма поиск в ширину может быть реализована при помощи очередей на языке C++ следующим образом. Код приведен в предположении, что граф хранится в формате сжатого списка смежности: для каждой вершины в массиве vertices_to_edges_ptrs хранятся индекс начала и индекс конца списка смежных с ней вершин из массива dst_ids.

// init distances
for(int i = 0; i < vertices_count; i++)
    _result[i] = MAX_INT;
    
// init queue and first vertex
std::queue<int> vertex_queue;
vertex_queue.push(_source_vertex);
_result[_source_vertex] = 1;
    
// do bfs
while(vertex_queue.size() > 0)
{
    int cur_vertex = vertex_queue.front();
    vertex_queue.pop();
        
    long long first = vertices_to_edges_ptrs[cur_vertex];
    long long last = vertices_to_edges_ptrs[cur_vertex + 1];
    for(long long i = first; i < last; i++)
    {
        int dst_id = dst_ids[i];
        if(_result[dst_id] == MAX_INT)
        {
            _result[dst_id] = _result[src_id] + 1;
            vertex_queue.push(dst_id);
        }
    }
}

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

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

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

Информационный граф классического алгоритма поиска в ширину приведен на рисунке 1.

Рисунок 1. Информационный граф алгоритма BFS.

На рисунке 1 используются следующие обозначения:

[1] - добавление вершины [math]u[/math] к множеству [math]F[/math].

[2] - извлечение добавленной вершины [math]v[/math] из множества [math]F[/math].

[3] - проверка расстояний до вершин, смежных с вершиной [math]v[/math].

[1] - добавление еще не посещенных вершин в множество [math]P[/math].

[4] - замена множества [math]F[/math] на [math]P[/math] и проверка его пустоты. В случае негустого множества - переход на следующую итерацию, иначе завершение работы алгоритма.

Данный алгоритм имеет один важный недостаток при реализации: операция [4] требует бесконфликтной возможности добавления элементов в множество P, что, на практике, всегда будет сводиться к сериализации обращений к структуре данных, моделирующих данное множество.

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

Рисунок 2. Информационный граф алгоритма BFS (независимые структуры данных).

Обозначения для рисунка 2:

[1] - добавление вершины-источника в множество [math]F[/math] .

[2] - разделение данных множества [math]F[/math] между процессами

[3] - помещение в множества [math]F_i[/math] соответствующих данных из [math]F[/math] каждым процессом с номером i.

[4] - извлечение очередной вершины из множеств [math]F_i[/math], обход её соседей и добавление их в множество [math]P_i[/math] в случае, если они еще не посещены

[5] - попарное слияние множеств [math]P_i[/math] для различных процессов, итоговое преобразование их в множество [math]F[/math].

[6] - проверка условия выхода из цикла

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

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

Входные данные: граф [math]G(V, E)[/math] ([math]n[/math] вершин [math]v_i[/math] и [math]m[/math] рёбер [math]e_j = (v^{(1)}_{j}, v^{(2)}_{j})[/math], вершина-источник [math]u[/math].

Объём входных данных: [math]O(m + n)[/math].

Выходные данные (возможные варианты):

для каждой вершины [math]v[/math] исходного графа расстояние [math]d(v)[/math], определенное как число ребер, лежащих на кратчайшем пути от вершины [math]u[/math] к [math]v[/math].
для каждой вершины [math]v[/math] исходного графа значение достижимости (достижима или нет) от вершины-источника [math]u[/math].

Объём выходных данных: [math]O(n)[/math].

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]