Алгоритм Крускала: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Daryin (обсуждение | вклад) |
Daryin (обсуждение | вклад) |
||
| Строка 34: | Строка 34: | ||
** функции <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> сочетают [[алгоритм Борувки]] и алгоритм Крускала. | ** функции <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> сочетают [[алгоритм Борувки]] и алгоритм Крускала. | ||
* Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.mst.minimum_spanning_tree.html minimum_spanning_tree]</code>). | * Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.mst.minimum_spanning_tree.html minimum_spanning_tree]</code>). | ||
* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/KruskalMinimumSpanningTree.html KruskalMinimumSpanningTree]</code>). | |||
== Литература == | == Литература == | ||
<references /> | <references /> | ||
Версия от 19:46, 11 июня 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].
Информационный граф
Описание ресурса параллелизма алгоритма
Описание входных и выходных данных
Свойства алгоритма
Программная реализация алгоритмов
Особенности реализации последовательного алгоритма
Описание локальности данных и вычислений
Возможные способы и особенности реализации параллельного алгоритма
Масштабируемость алгоритма и его реализации
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
- 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.