Алгоритм Крускала: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Daryin (обсуждение | вклад) |
Daryin (обсуждение | вклад) |
||
| Строка 9: | Строка 9: | ||
=== Описание схемы реализации последовательного алгоритма === | === Описание схемы реализации последовательного алгоритма === | ||
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
Время работы алгоритма складывается из сортировки рёбер и поддержания информации о фрагментах. В базовом варианте рёбра вначале сортируются за время <math>m \ln m</math>, затем просматриваются в порядке увеличения веса за время <math>O(m)</math> (например, с помощью быстрой сортировки), при этом для хранения информации о текущих фрагментах используется [[система непересекающихся множеств]]<ref>Tarjan, Robert Endre. “Efficiency of a Good but Not Linear Set Union Algorithm.” Journal of the ACM 22, no. 2 (April 1975): 215–25. doi:10.1145/321879.321884.</ref> с общим временем работы <math>O(m \alpha(m, n))</math>. Итоговая сложность алгоритма <math>O(m \ln m)</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> (англ. IQS: Incremental Quick Sort) позволяет снизить затраты на сортировку, так что среднее время работы алгоритма составляет <math>O(m + n \ln^2 n)</math>. | |||
В случае, если рёбра графа изначально отсортированы по весу рёбер, сложность алгоритма снижается до <math>O(m \alpha(m, n))</math>. | |||
=== Информационный граф === | === Информационный граф === | ||
=== Описание ресурса параллелизма алгоритма === | === Описание ресурса параллелизма алгоритма === | ||
Версия от 22:50, 10 июня 2015
Свойства и структура алгоритмов
Общее описание алгоритма
Алгоритм Крускала[1] предназначен для решения задачи о построении минимального остовного дерева во взвешенном неориентированном графе. В отличие от алгоритмов Прима и Борувки, алгоритм Крускала не требует информации о рёбрах конкретной вершины, вместо этого на его вход подаётся общий список рёбер графа в произвольном порядке. Кроме этого, каждое (ненаправленное) ребро достаточно представить лишь одной из его направленных дуг, что на практике означает в два раза меньший объём вычислений. Последовательная версия алгоритма Крускала работает, как правило, быстрее последовательной версии алгоритма Борувки, а при условии предварительной сортировки списка рёбер по весу сложность алгоритма снижается до [math]\displaystyle{ O(m \alpha(m, n)) }[/math].
Математическое описание
Вычислительное ядро алгоритма
Макроструктура алгоритма
Описание схемы реализации последовательного алгоритма
Последовательная сложность алгоритма
Время работы алгоритма складывается из сортировки рёбер и поддержания информации о фрагментах. В базовом варианте рёбра вначале сортируются за время [math]\displaystyle{ m \ln m }[/math], затем просматриваются в порядке увеличения веса за время [math]\displaystyle{ O(m) }[/math] (например, с помощью быстрой сортировки), при этом для хранения информации о текущих фрагментах используется система непересекающихся множеств[2] с общим временем работы [math]\displaystyle{ O(m \alpha(m, n)) }[/math]. Итоговая сложность алгоритма [math]\displaystyle{ O(m \ln m) }[/math].
Как видно, наибольшую сложность имеет этап сортировки, при этом большая часть рёбер сортируется напрасно: они всё равно будут отброшены, как принадлежащие одному фрагменту. Использование инкрементальной быстрой сортировки[3] (англ. IQS: Incremental Quick Sort) позволяет снизить затраты на сортировку, так что среднее время работы алгоритма составляет [math]\displaystyle{ O(m + n \ln^2 n) }[/math].
В случае, если рёбра графа изначально отсортированы по весу рёбер, сложность алгоритма снижается до [math]\displaystyle{ O(m \alpha(m, n)) }[/math].
Информационный граф
Описание ресурса параллелизма алгоритма
Описание входных и выходных данных
Свойства алгоритма
Программная реализация алгоритмов
Особенности реализации последовательного алгоритма
Описание локальности данных и вычислений
Возможные способы и особенности реализации параллельного алгоритма
Масштабируемость алгоритма и его реализации
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
Литература
- ↑ Kruskal, Joseph B. “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem.” Proceedings of the American Mathematical Society 7, no. 1 (January 1956): 48–50. doi:10.1090/S0002-9939-1956-0078686-7.
- ↑ Tarjan, Robert Endre. “Efficiency of a Good but Not Linear Set Union Algorithm.” Journal of the ACM 22, no. 2 (April 1975): 215–25. doi:10.1145/321879.321884.
- ↑ 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.