Алгоритм Крускала
Свойства и структура алгоритмов
Общее описание алгоритма
Алгоритм Крускала[1] предназначен для решения задачи о построении минимального остовного дерева во взвешенном неориентированном графе. Последовательная сложность алгоритма [math]\displaystyle{ O(m \ln n) }[/math].
В отличие от алгоритмов Прима и Борувки, алгоритм Крускала не требует информации о рёбрах конкретной вершины, вместо этого на его вход подаётся общий список рёбер графа в произвольном порядке. Кроме этого, каждое (ненаправленное) ребро достаточно представить лишь одной из его направленных дуг, что на практике означает в два раза меньший объём вычислений. Последовательная версия алгоритма Крускала работает, как правило, быстрее последовательной версии алгоритма Борувки, а при условии предварительной сортировки списка рёбер по весу сложность алгоритма снижается до [math]\displaystyle{ O(m \alpha(m, n)) }[/math].
Математическое описание
Вычислительное ядро алгоритма
Макроструктура алгоритма
Описание схемы реализации последовательного алгоритма
Последовательная сложность алгоритма
Время работы алгоритма складывается из сортировки рёбер и поддержания информации о фрагментах. В базовом варианте рёбра вначале сортируются за время [math]\displaystyle{ m \ln n }[/math] (например, с помощью быстрой сортировки), затем просматриваются в порядке увеличения веса за время [math]\displaystyle{ O(m) }[/math], при этом для хранения информации о текущих фрагментах используется система непересекающихся множеств[2] с общим временем работы [math]\displaystyle{ O(m \alpha(m, n)) }[/math]. Итоговая сложность алгоритма [math]\displaystyle{ O(m \ln n) }[/math].
Как видно, наибольшую сложность имеет этап сортировки, при этом большая часть рёбер сортируется напрасно: они всё равно будут отброшены, как принадлежащие одному фрагменту. Использование инкрементальной быстрой сортировки[3] (англ. IQS: Incremental Quick Sort) позволяет снизить затраты на сортировку, так что среднее время работы алгоритма составляет [math]\displaystyle{ O(m + n \ln^2 n) }[/math].
В случае, если рёбра графа изначально отсортированы по весу рёбер, сложность алгоритма снижается до [math]\displaystyle{ O(m \alpha(m, n)) }[/math].
Информационный граф
Описание ресурса параллелизма алгоритма
Описание входных и выходных данных
Свойства алгоритма
Программная реализация алгоритмов
Особенности реализации последовательного алгоритма
Описание локальности данных и вычислений
Возможные способы и особенности реализации параллельного алгоритма
Масштабируемость алгоритма и его реализации
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
- C++: Boost Graph Library (функция
kruskal_min_spanning_tree), сложность [math]\displaystyle{ O(m \ln m) }[/math]. - C++, MPI: Parallel Boost Graph Library
- функция
merge_local_minimum_spanning_treesреализует алгоритм Крускала; - функции
dense_boruvka_minimum_spanning_tree,boruvka_then_merge,boruvka_mixed_mergeсочетают алгоритм Борувки и алгоритм Крускала.
- функция
- Python: NetworkX (функция
minimum_spanning_tree). - Java: JGraphT (класс
KruskalMinimumSpanningTree).
Литература
- ↑ 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.