Алгоритм Прима: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [непроверенная версия] |
Daryin (обсуждение | вклад) |
Daryin (обсуждение | вклад) |
||
| Строка 9: | Строка 9: | ||
=== Описание схемы реализации последовательного алгоритма === | === Описание схемы реализации последовательного алгоритма === | ||
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
Основной объём вычислений в алгоритме Прима приходится на поддержание набора рёбер, выходящих из текущего фрагмента. Необходимо добавлять новые рёбра или вершины в набор, и находить ребро с наименьшим весом. | |||
* При использовании списков вершин сложность <math>O(n^2)</math>. | |||
* При использовании бинарной кучи рёбер сложность <math>O(m \ln m)</math>. | |||
* При использовании бинарной кучи вершин и сортировке рёбер у каждой вершины сложность <math>O(m \ln n)</math>. | |||
* При использовании быстрой кучи<ref>Navarro, Gonzalo, and Rodrigo Paredes. “On Sorting, Heaps, and Minimum Spanning Trees.” Algorithmica 57, no. 4 (March 23, 2010): 585–620. doi:10.1007/s00453-010-9400-6.</ref> сложность <math>O(m + n \ln^2 n)</math>. | |||
* При использовании фибоначчиевой кучи<ref>Fredman, Michael L, and Robert Endre Tarjan. “Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms.” Journal of the ACM 34, no. 3 (July 1987): 596–615. doi:10.1145/28869.28874.</ref> сложность <math>O(m + n \ln n)</math>. | |||
=== Информационный граф === | === Информационный граф === | ||
=== Описание ресурса параллелизма алгоритма === | === Описание ресурса параллелизма алгоритма === | ||
Версия от 23:06, 10 июня 2015
Свойства и структура алгоритмов
Общее описание алгоритма
Алгоритм Прима[1][2] предназначен для решения задачи о построении минимального остовного дерева во взвешенном неориентированном графе.
Математическое описание
Вычислительное ядро алгоритма
Макроструктура алгоритма
Описание схемы реализации последовательного алгоритма
Последовательная сложность алгоритма
Основной объём вычислений в алгоритме Прима приходится на поддержание набора рёбер, выходящих из текущего фрагмента. Необходимо добавлять новые рёбра или вершины в набор, и находить ребро с наименьшим весом.
- При использовании списков вершин сложность [math]\displaystyle{ O(n^2) }[/math].
- При использовании бинарной кучи рёбер сложность [math]\displaystyle{ O(m \ln m) }[/math].
- При использовании бинарной кучи вершин и сортировке рёбер у каждой вершины сложность [math]\displaystyle{ O(m \ln n) }[/math].
- При использовании быстрой кучи[3] сложность [math]\displaystyle{ O(m + n \ln^2 n) }[/math].
- При использовании фибоначчиевой кучи[4] сложность [math]\displaystyle{ O(m + n \ln n) }[/math].
Информационный граф
Описание ресурса параллелизма алгоритма
Описание входных и выходных данных
Свойства алгоритма
Программная реализация алгоритмов
Особенности реализации последовательного алгоритма
Описание локальности данных и вычислений
Возможные способы и особенности реализации параллельного алгоритма
Масштабируемость алгоритма и его реализации
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
- Boost Graph Library (функция
prim_minimum_spanning_tree), сложность [math]\displaystyle{ O(m \ln n) }[/math].
Литература
- ↑ Prim, R C. “Shortest Connection Networks and Some Generalizations.” Bell System Technical Journal 36, no. 6 (November 1957): 1389–1401. doi:10.1002/j.1538-7305.1957.tb01515.x.
- ↑ Dijkstra, E W. “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1, no. 1 (December 1959): 269–71. doi:10.1007/BF01386390.
- ↑ Navarro, Gonzalo, and Rodrigo Paredes. “On Sorting, Heaps, and Minimum Spanning Trees.” Algorithmica 57, no. 4 (March 23, 2010): 585–620. doi:10.1007/s00453-010-9400-6.
- ↑ Fredman, Michael L, and Robert Endre Tarjan. “Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms.” Journal of the ACM 34, no. 3 (July 1987): 596–615. doi:10.1145/28869.28874.