Поиск в ширину (BFS)
Алгоритм поиска в ширину (BFS) | |
Последовательный алгоритм | |
Последовательная сложность | O(|V| + |E|) |
Объём входных данных | O(|V| + |E|) |
Объём выходных данных | O(|V|) |
Параллельный алгоритм | |
Высота ярусно-параллельной формы | N/A, \max O(|V|) |
Ширина ярусно-параллельной формы | N/A, \max O(|E|) |
Основные авторы описания: И.В.Афанасьев
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 3 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Поиск в ширину (англ. Breadth-First Search, BFS) позволяет вычислить кратчайшие расстояния (в терминах количества рёбер) от выделенной вершины ориентированного графа до всех остальных вершин, и/или построить корневое направленное дерево, расстояния в котором совпадают с расстояниями в исходном графе. Кроме того, поиск в ширину позволяет решать задачу проверки достижимости (существуют ли пути между вершиной источником и остальными вершинами графа). Впервые алгоритм поиска в ширину описан в работах Мура[1] и Ли[2].
Алгоритм основан на обходе вершин графа "по слоям". На каждом шаге есть множество "передовых" вершин, для смежных к которым производится проверка, относятся ли они к еще не посещенным. Все еще не посещенные вершины добавляются в новое множество "передовых" вершин, обрабатываемых на следующем шаге. Изначально в множество "передовых" вершин входит только вершина-источник, от которой и начинается обход.
В последовательном случае алгоритм имеет алгоритмическую сложность O(|V| + |E|), где |V| - число вершин в графе, |E| - число ребер в графе.
1.2 Математическое описание алгоритма
Пусть задан граф G = (V, E) без весов, и с выделенной вершиной-источником u. Путем P(u,v) между вершинами u и v называется множество ребер (u, v_1), (v_1, v_2), ... (v_{n-1}, v). Длиной пути d(u,v) обозначим число ребер в данном пути между вершинами u и v. Поиск в ширину находит кратчайшие пути d(u,v) от вершины u до всех остальных вершин графа описанным далее образом.
В начале работы алгоритма расстояние до вершины-источника d(u)=0, до остальных вершин d(v) = \infty, \forall v \neq u . Также в начале работы алгоритма инициализируется множество F = \{u\}.
Далее на каждом шаге алгоритма строится множество вершин P = {w} , таких, что для \forall v \in F \exists (v, w) \in E | d(w) = \infty , при этом обновляются расстояния d(w)=d(v)+1 для \forall w \in P . Затем производится переход на следующий шаг до тех пор, пока P \neq \emptyset; при этом в начале каждого шага множество F заменяется на P.
1.3 Вычислительное ядро алгоритма
Вычислительным ядром алгоритма является обход вершин, смежных с выбранной вершиной v, с последующим добавлением еще не посещенных вершин в множество P. Данная операция выполняется на каждом шаге для каждой вершины v \in F.
1.4 Макроструктура алгоритма
Алгоритм последовательно уточняет значения функции d(v).
Структуру можно описать следующим образом:
1. Инициализация: всем вершинам присваивается предполагаемое расстояние d(v)=\infty, кроме вершины-источника, для которой d(u)=0 .
2. Помещение вершины источника v в множество "передовых" вершин F.
3. Обход вершин множества F.
а) Инициализация множества P=\emptyset.
б) Для каждой вершины v \in F обход всех вершин w | \exists (v, w) (смежных с ней), c помещением в множество P таких вершин w | d(w)=\infty.
в) Замена множества F на P и переход на шаг 3 в случае, если множество F \neq \emptyset.
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 Последовательная сложность алгоритма
Алгоритм имеет последовательную сложность O(|V| + |E|), где |V| и |E| - число вершин и ребер графа соответственно: алгоритм инициализирует начальный массив расстояний - O(|V|) операций, а затем обходит каждую вершину один единственный раз - O(|E|) операций. Данная оценка верна в случае, если формат хранения графа позволяет обходить вершины, смежные к выбранной (к примеру форматы списка смежности, сжатого списка смежности). При использовании других форматов оценка сложности может быть большей.
1.7 Информационный граф
Информационный граф классического алгоритма поиска в ширину приведен на рисунке 1.
На рисунке 1 используются следующие обозначения:
[1] - добавление вершины-источника u к множеству F.
[2] - извлечение добавленной вершины v из множества F.
[3] - проверка расстояний до вершин, смежных с вершиной v.
[4] - добавление еще не посещенных вершин в множество P.
[5] - замена множества F на P и проверка его пустоты. В случае непустого множества - переход на следующую итерацию, иначе завершение работы алгоритма.
Данный алгоритм имеет один важный недостаток при реализации: операция [4] требует бесконфликтной возможности добавления элементов в множество P, что, на практике, всегда будет сводиться к сериализации обращений к структуре данных, моделирующей данное множество.
В результате часто используется модификация алгоритма (далее алгоритм-2), использующая набор независимых структур данных для каждого из параллельных процессов. Информационный граф данного подхода приведен на рисунке 2.
Обозначения для рисунка 2:
[1] - добавление вершины-источника в множество F.
[2] - разделение данных множества F между процессами
[3] - помещение в множества F_i соответствующих данных из F каждым процессом с номером i.
[4] - извлечение очередной вершины из множеств F_i, обход её соседей и добавление их в множество P_i в случае, если они еще не посещены
[5] - попарное слияние множеств P_i для различных процессов, итоговое преобразование их в множество F.
[6] - проверка условия выхода из цикла
Кроме того, в случае, если реализация структур данных, моделирующих множества F и P, невозможна, может использоваться квадратичный по сложности алгоритм, схожий с алгоритм Беллмана-Форда. Основная идея заключается в том, что на каждом шаге производится обход всех ребер графа с обновлением текущего массива дистанций. Информационный граф данной модификации алгоритма приведен на рисунке 3.
Обозначения для рисунка 3:
[1] - инициализация расстояний до вершины-источника
[2] - инициализация расстояний до остальных вершин графа
[3] - загрузка информации об очередном ребре и обновление дистанций до соответствующих вершин.
[4] - проверка условия выхода из цикла
1.8 Ресурс параллелизма алгоритма
В ходе работы классический вариант алгоритма обходит граф по слоям. В каждый слой добавляются еще не посещенные вершины, достижимые из вершин предыдущего слоя. Обход вершин каждого слоя, как и их соседей, может производиться параллельно. Точно оценить число вершин в каждом слое невозможно в силу того, что их количество зависит от структуры связанности входного графа. Аналогично невозможно оценить число шагов алгоритма, за которое будут найдены все кратчайшие пути.
Произведем оценку ширины ярусно-параллельной формы алгоритма через максимальное число вершин p в слое среди всех шагов алгоритма. Тогда число параллельных операций на данном слое будет равно сумме числа смежных вершин для каждой вершины слоя: \sum_{n=1}^{p} degree(v_i), при этом для каждого слоя данное значение будет различным. Высота ярусно-параллельной формы будет равна числу шагов в алгоритме и может быть оценена только сверху (не более |V|).
При квадратичном подходе к параллельной реализации алгоритма на каждом шаге выполняется O(|E|) операций, которые могут быть выполнены параллельно; таким образом, ширина ЯПФ данной модификации алгоритма равна O(|E|). Число шагов алгоритма, как и в классическом случае, зависит от структуры графа и может быть оценено сверху как O(|V|).
1.9 Входные и выходные данные алгоритма
Входные данные: граф G(V, E), |V| вершин v_i и |E| рёбер e_j = (v^{(1)}_{j}, v^{(2)}_{j}), вершина-источник u.
Объём входных данных: O(|V| + |E|).
Выходные данные (возможные варианты):
- для каждой вершины v исходного графа расстояние d(v), определенное как число ребер, лежащих на кратчайшем пути от вершины u к v.
- для каждой вершины v исходного графа значение достижимости (достижима или нет) от вершины-источника u.
Объём выходных данных: O(|V|).