Уровень алгоритма

Anton121 Test Buttons: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 12: Строка 12:
 
{{PushButton|link = https://yandex.ru/|text = Yandex|size = 100px}}  
 
{{PushButton|link = https://yandex.ru/|text = Yandex|size = 100px}}  
 
{{PushButton|link = https://yandex.ru/|text = Yandex|size = 100px|weight = bold|decoration = underline|color = orange}}
 
{{PushButton|link = https://yandex.ru/|text = Yandex|size = 100px|weight = bold|decoration = underline|color = orange}}
 +
<br>
 +
{{algorithm
 +
| name              = Алгоритм поиска в ширину (BFS)
 +
| serial_complexity = <math>O(|V| + |E|)</math>
 +
| pf_height        = <math>N/A, \max O(|V|) </math>
 +
| pf_width          = <math>N/A, \max O(|E|) </math>
 +
| input_data        = <math>O(|V| + |E|)</math>
 +
| output_data      = <math>O(|V|)</math>
 +
}}
 +
 +
Основные авторы описания: [[Участник:Elijah|И.В.Афанасьев]]
 +
 +
== Свойства и структура алгоритма ==
 +
 +
=== Общее описание алгоритма ===
 +
 +
'''Поиск в ширину''' (англ. Breadth-First Search, BFS) позволяет вычислить кратчайшие расстояния (в терминах количества рёбер) от выделенной вершины ориентированного графа до всех остальных вершин, и/или построить корневое направленное дерево, расстояния в котором совпадают с расстояниями в исходном графе. Кроме того, поиск в ширину позволяет решать задачу проверки достижимости (существуют ли пути между вершиной источником и остальными вершинами графа). Впервые алгоритм поиска в ширину описан в работах Мура<ref>Moore, Edward F. “The Shortest Path Through a Maze,” International Symposium on the Theory of Switching, 285–92, 1959.</ref> и Ли<ref>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.</ref>.
 +
 +
Алгоритм основан на обходе вершин графа "по слоям". На каждом шаге есть множество "передовых" вершин, для смежных к которым производится проверка, относятся ли они к еще не посещенным. Все еще не посещенные вершины добавляются в новое множество "передовых" вершин, обрабатываемых на следующем шаге. Изначально в множество "передовых" вершин входит только вершина-источник, от которой и начинается обход.
 +
 +
В последовательном случае алгоритм имеет алгоритмическую сложность <math>O(|V| + |E|)</math>, где <math>|V|</math> - число вершин в графе, <math>|E|</math> - число ребер в графе.
 +
 +
=== Математическое описание алгоритма ===
 +
 +
Пусть задан граф <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.
 +
 +
=== Вычислительное ядро алгоритма ===
 +
 +
Вычислительным ядром алгоритма является обход вершин, смежных с выбранной вершиной <math>v</math>, с последующим добавлением еще не посещенных вершин в множество <math>P</math>. Данная операция выполняется на каждом шаге для каждой вершины <math>v \in F</math>.
 +
 +
=== Макроструктура алгоритма ===
 +
 +
Алгоритм последовательно уточняет значения функции <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>.
 +
 +
=== Схема реализации последовательного алгоритма ===
 +
 +
Простейшая версия алгоритма поиск в ширину может быть реализована при помощи очередей на языке C++ следующим образом.
 +
Код приведен в предположении, что граф хранится в формате сжатого списка смежности: для каждой вершины в массиве vertices_to_edges_ptrs хранятся индекс начала и индекс конца списка смежных с ней вершин из массива dst_ids.
 +
 +
<source lang="C++">
 +
 +
// 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);
 +
        }
 +
    }
 +
}
 +
 +
</source>
 +
 +
=== Последовательная сложность алгоритма ===
 +
 +
Алгоритм имеет последовательную сложность <math>O(|V| + |E|)</math>, где <math>|V|</math> и <math>|E|</math> - число вершин и ребер графа соответственно: алгоритм инициализирует начальный массив расстояний - <math>O(|V|)</math> операций, а затем обходит каждую вершину один единственный раз -  <math>O(|E|)</math> операций. Данная оценка верна в случае, если формат хранения графа позволяет обходить вершины, смежные к выбранной (к примеру форматы списка смежности, сжатого списка смежности). При использовании других форматов оценка сложности может быть большей.
 +
 +
=== Информационный граф ===
 +
 +
Информационный граф классического алгоритма поиска в ширину приведен на рисунке 1.
 +
 +
[[Файл:Classical_BFS_ig.png|thumb|center|500px|Рисунок 1. Информационный граф алгоритма BFS.]]
 +
 +
На рисунке 1 используются следующие обозначения:
 +
 +
[1] - добавление вершины-источника <math>u</math> к множеству <math>F</math>.
 +
 +
[2] - извлечение добавленной вершины <math>v</math> из множества <math>F</math>.
 +
 +
[3] - проверка расстояний до вершин, смежных с вершиной <math>v</math>.
 +
 +
[4] - добавление еще не посещенных вершин в множество <math>P</math>.
 +
 +
[5] - замена множества <math>F</math> на  <math>P</math> и проверка его пустоты. В случае непустого множества - переход на следующую итерацию, иначе завершение работы алгоритма.
 +
 +
Данный алгоритм имеет один важный недостаток при реализации: операция [4] требует бесконфликтной возможности добавления элементов в множество P, что, на практике, всегда будет сводиться к сериализации обращений к структуре данных, моделирующей данное множество.
 +
 +
В результате часто используется модификация алгоритма (далее алгоритм-2), использующая набор независимых структур данных для каждого из параллельных процессов. Информационный граф данного подхода приведен на рисунке 2.
 +
 +
[[Файл:BFS_ig_parallel_queues.png|thumb|center|500px|Рисунок 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] - проверка условия выхода из цикла
 +
 +
Кроме того, в случае, если реализация структур данных, моделирующих множества <math>F</math> и <math>P</math>, невозможна, может использоваться квадратичный по сложности алгоритм, схожий с алгоритм Беллмана-Форда. Основная идея заключается в том, что на каждом шаге производится обход всех ребер графа с обновлением текущего массива дистанций. Информационный граф данной модификации алгоритма приведен на рисунке 3.
 +
 +
[[Файл:quadratic_BFS_ig.png|thumb|center|500px|Рисунок 3. Информационный граф алгоритма BFS (квадратичный подход к распараллеливанию).]]
 +
 +
Обозначения для рисунка 3:
 +
 +
[1] - инициализация расстояний до вершины-источника
 +
 +
[2] - инициализация расстояний до остальных вершин графа
 +
 +
[3] - загрузка информации об очередном ребре и обновление дистанций до соответствующих вершин.
 +
 +
[4] - проверка условия выхода из цикла
 +
 +
=== Ресурс параллелизма алгоритма ===
 +
 +
В ходе работы классический вариант алгоритма обходит граф по слоям. В каждый слой добавляются еще не посещенные вершины, достижимые из вершин предыдущего слоя. Обход вершин каждого слоя, как и их соседей, может производиться параллельно. Точно оценить число вершин в каждом слое невозможно в силу того, что их количество зависит от структуры связанности входного графа. Аналогично невозможно оценить число шагов алгоритма, за которое будут найдены все кратчайшие пути.
 +
 +
Произведем оценку ширины ярусно-параллельной формы алгоритма через максимальное число вершин p в слое среди всех шагов алгоритма. Тогда число параллельных операций на данном слое будет равно сумме числа смежных вершин для каждой вершины слоя: <math>\sum_{n=1}^{p} degree(v_i)</math>, при этом для каждого слоя данное значение будет различным. Высота ярусно-параллельной формы будет равна числу шагов в алгоритме и может быть оценена только сверху (не более <math>|V|</math>).
 +
 +
При квадратичном подходе к параллельной реализации алгоритма на каждом шаге выполняется <math>O(|E|)</math> операций, которые могут быть выполнены параллельно; таким образом, ширина ЯПФ данной модификации алгоритма равна <math>O(|E|)</math>. Число шагов алгоритма, как и в классическом случае, зависит от структуры графа и может быть оценено сверху как <math>O(|V|)</math>.
 +
 +
=== Входные и выходные данные алгоритма ===
 +
'''Входные данные''': граф <math>G(V, E)</math>, <math>|V|</math> вершин <math>v_i</math> и <math>|E|</math> рёбер <math>e_j = (v^{(1)}_{j}, v^{(2)}_{j})</math>, вершина-источник <math>u</math>.
 +
 +
'''Объём входных данных''': <math>O(|V| + |E|)</math>.
 +
 +
'''Выходные данные''' (возможные варианты):
 +
# для каждой вершины <math>v</math> исходного графа расстояние <math>d(v)</math>, определенное как число ребер, лежащих на кратчайшем пути от вершины <math>u</math> к <math>v</math>.
 +
# для каждой вершины <math>v</math> исходного графа значение достижимости (достижима или нет) от вершины-источника <math>u</math>.
 +
 +
'''Объём выходных данных''': <math>O(|V|)</math>.
 +
 +
=== Свойства алгоритма ===
 +
 +
== Программная реализация алгоритма ==
 +
=== Особенности реализации последовательного алгоритма ===
 +
=== Локальность данных и вычислений ===
 +
==== Локальность реализации алгоритма ====
 +
===== Структура обращений в память и качественная оценка локальности =====
 +
===== Количественная оценка локальности =====
 +
=== Возможные способы и особенности параллельной реализации алгоритма ===
 +
=== Масштабируемость алгоритма и его реализации ===
 +
==== Масштабируемость алгоритма ====
 +
==== Масштабируемость реализации алгоритма ====
 +
=== Динамические характеристики и эффективность реализации алгоритма ===
 +
=== Выводы для классов архитектур ===
 +
=== Существующие реализации алгоритма ===
 +
 +
* Распределённый алгоритм поиска вширь является вычислительным ядром бенчмарка [http://www.graph500.org Graph500].
 +
** MPI: {{Buttonlinkimp|12}}
 +
* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функции <code>[http://www.boost.org/libs/graph/doc/breadth_first_search.html breadth_first_search]</code>, <code>[http://www.boost.org/libs/graph/doc/breadth_first_visit.html breadth_first_visit]</code>).
 +
* C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/breadth_first_search.html breadth_first_search]</code>).{{Buttonlinkimp|11}}
 +
* Java: [http://webgraph.di.unimi.it WebGraph] (класс <code>[http://webgraph.di.unimi.it/docs/it/unimi/dsi/webgraph/algo/ParallelBreadthFirstVisit.html ParallelBreadthFirstVisit]</code>), многопоточная реализация.
 +
* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.traversal.breadth_first_search.bfs_edges.html bfs_edges]</code>).
 +
* Python/C++: [https://networkit.iti.kit.edu NetworKit] (класс <code>[https://networkit.iti.kit.edu/data/uploads/docs/NetworKit-Doc/python/html/graph.html#networkit.graph.BFS networkit.graph.BFS]</code>).
 +
* RCC for CPU {{Buttonlinkimp|9}}
 +
* RCC for GPU {{Buttonlinkimp|26}}
 +
* Gap {{Buttonlinkimp|36}}
 +
* Litra {{Buttonlinkimp|39}}
 +
== Литература ==
 +
 +
<references />
 +
 +
[[Категория:Статьи в работе]]
 +
 +
[[En:Breadth-first search (BFS)]]

Версия 16:00, 7 ноября 2021

Содержание

1 LinkButtons

Все кнопки ниже ведут на "yandex.ru" (Просто показано их разное "оформление")
Yandex Yandex Yandex Yandex Yandex Yandex

Yandex Yandex


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


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

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

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

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

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

В последовательном случае алгоритм имеет алгоритмическую сложность O(|V| + |E|), где |V| - число вершин в графе, |E| - число ребер в графе.

2.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.

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

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

2.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.

2.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);
        }
    }
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Объём входных данных: O(|V| + |E|).

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

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

Объём выходных данных: O(|V|).

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

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

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

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

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

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

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

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

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

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

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

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

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

4 Литература

  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.
Источник — https://algowiki-project.org/w/ru/index.php?title=Anton121_Test_Buttons&oldid=28669