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

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

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

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

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

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

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

В последовательном случае алгоритм имеет алгоритмическую сложность [math]\displaystyle{ O(|V| + |E|) }[/math], где [math]\displaystyle{ |V| }[/math] - число вершин в графе, [math]\displaystyle{ |E| }[/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) = \infty, \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) = \infty }[/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].

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

Простейшая версия алгоритма поиск в ширину может быть реализована при помощи очередей на языке 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);
        }
    }
}

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

Алгоритм имеет последовательную сложность [math]\displaystyle{ O(|V| + |E|) }[/math], где [math]\displaystyle{ |V| }[/math] и [math]\displaystyle{ |E| }[/math] - число вершин и ребер графа соответственно: алгоритм инициализирует начальный массив расстояний - [math]\displaystyle{ O(|V|) }[/math] операций, а затем обходит каждую вершину один единственный раз - [math]\displaystyle{ O(|E|) }[/math] операций. Данная оценка верна в случае, если формат хранения графа позволяет обходить вершины, смежные к выбранной (к примеру форматы списка смежности, сжатого списка смежности). При использовании других форматов оценка сложности может быть большей.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Кроме того, в случае, если реализация структур данных, моделирующих множества [math]\displaystyle{ F }[/math] и [math]\displaystyle{ P }[/math], невозможна, может использоваться квадратичный по сложности алгоритм, схожий с алгоритм Беллмана-Форда. Основная идея заключается в том, что на каждом шаге производится обход всех ребер графа с обновлением текущего массива дистанций. Информационный граф данной модификации алгоритма приведен на рисунке 3.

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

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

[1] - инициализация расстояний до вершины-источника

[2] - инициализация расстояний до остальных вершин графа

[3] - загрузка информации об очередном ребре и обновление дистанций до соответствующих вершин.

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

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

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

Произведем оценку ширины ярусно-параллельной формы алгоритма через максимальное число вершин p в слое среди всех шагов алгоритма. Тогда число параллельных операций на данном слое будет равно сумме числа смежных вершин для каждой вершины слоя: [math]\displaystyle{ \sum_{n=1}^{p} degree(v_i) }[/math], при этом для каждого слоя данное значение будет различным. Высота ярусно-параллельной формы будет равна числу шагов в алгоритме и может быть оценена только сверху (не более [math]\displaystyle{ |V| }[/math]).

При квадратичном подходе к параллельной реализации алгоритма на каждом шаге выполняется [math]\displaystyle{ O(|E|) }[/math] операций, которые могут быть выполнены параллельно; таким образом, ширина ЯПФ данной модификации алгоритма равна [math]\displaystyle{ O(|E|) }[/math]. Число шагов алгоритма, как и в классическом случае, зависит от структуры графа и может быть оценено сверху как [math]\displaystyle{ O(|V|) }[/math].

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

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

Объём входных данных: [math]\displaystyle{ O(|V| + |E|) }[/math].

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

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

Объём выходных данных: [math]\displaystyle{ O(|V|) }[/math].