Алгоритм Борувки: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [непроверенная версия] |
Daryin (обсуждение | вклад) |
Daryin (обсуждение | вклад) |
||
| Строка 22: | Строка 22: | ||
=== Существующие реализации алгоритма === | === Существующие реализации алгоритма === | ||
* 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/dehne_gotz_min_spanning_tree.html#dense-boruvka-minimum-spanning-tree dense_boruvka_minimum_spanning_tree]</code>, <code>[http://www.boost.org/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html# | * 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/dehne_gotz_min_spanning_tree.html#dense-boruvka-minimum-spanning-tree dense_boruvka_minimum_spanning_tree]</code>, <code>[http://www.boost.org/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html#boruvka-then-merge boruvka_then_merge]</code>, <code>[http://www.boost.org/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html#boruvka-mixed-merge boruvka_mixed_merge]</code> сочетают алгоритм Борувки и [[алгоритм Крускала]]. | ||
== Литература == | == Литература == | ||
<references /> | <references /> | ||
Версия от 16:57, 11 июня 2015
Свойства и структура алгоритмов
Общее описание алгоритма
Алгоритм Борувки[1][2] предназначен для решения задачи о построении минимального остовного дерева во взвешенном неориентированном графе. Алгоритм хорошо параллелизуется и является основой для распределённого алгоритма GHS.
Математическое описание
Вычислительное ядро алгоритма
Макроструктура алгоритма
Описание схемы реализации последовательного алгоритма
Последовательная сложность алгоритма
Информационный граф
Описание ресурса параллелизма алгоритма
Описание входных и выходных данных
Свойства алгоритма
Программная реализация алгоритмов
Особенности реализации последовательного алгоритма
Описание локальности данных и вычислений
Возможные способы и особенности реализации параллельного алгоритма
Масштабируемость алгоритма и его реализации
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
- C++, MPI: Parallel Boost Graph Library; функции
dense_boruvka_minimum_spanning_tree,boruvka_then_merge,boruvka_mixed_mergeсочетают алгоритм Борувки и алгоритм Крускала.