Алгоритм Крускала: различия между версиями

[непроверенная версия]

[досмотренная версия]

Текущая версия на 10:03, 6 июля 2022

Содержание

1 Свойства и структура алгоритма
2 Программная реализация алгоритма
3 Литература

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Алгоритм Крускала^[1] предназначен для решения задачи о построении минимального остовного дерева во взвешенном неориентированном графе. Последовательная сложность алгоритма [math]O(m \ln n)[/math].

В отличие от алгоритмов Прима и Борувки, алгоритм Крускала не требует информации о рёбрах конкретной вершины, вместо этого на его вход подаётся общий список рёбер графа в произвольном порядке. Кроме этого, каждое (ненаправленное) ребро достаточно представить лишь одной из его направленных дуг, что на практике означает в два раза меньший объём вычислений. Последовательная версия алгоритма Крускала работает, как правило, быстрее последовательной версии алгоритма Борувки, а при условии предварительной сортировки списка рёбер по весу сложность алгоритма снижается до [math]O(m \alpha(m, n))[/math].

1.2 Математическое описание алгоритма

Пусть задан связный неориентированный граф [math]G = (V, E)[/math] с весами рёбер [math]f(e)[/math]. Предполагается, что веса всех рёбер различны (если это не так, то можно упорядочить рёбра сначала по весу, а потом по номеру).

Алгоритм Крускала основан на следующих двух свойствах задачи:

Минимальное ребро графа. Если [math]e^*[/math] – единственное ребро графа с минимальным весом, то оно принадлежит минимальному остовному дереву..
Схлопывание фрагментов. Пусть [math]F[/math] – фрагмент минимального остовного дерева графа [math]G[/math], а граф [math]G'[/math] получен из [math]G[/math] склеиванием вершин, принадлежащих [math]F[/math]. Тогда объединение [math]F[/math] и минимального остовного дерева графа [math]G'[/math] даёт минимальное остовное дерево исходного графа [math]G[/math].

В начале работы алгоритма каждая вершина графа [math]G[/math] является отдельным фрагментом. На каждом шаге из рёбер, ещё не рассмотренных на предыдущих шагах, выбирается ребро с минимальным весом. Если оно соединяет два различных фрагмента, то оно добавляется в минимальное остовное дерево, а фрагменты склеиваются. В противном случае это ребро отбрасывается.

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

Время работы алгоритма складывается из сортировки рёбер и поддержания информации о фрагментах. В базовом варианте рёбра вначале сортируются за время [math]m \ln n[/math] (например, с помощью быстрой сортировки), затем просматриваются в порядке увеличения веса за время [math]O(m)[/math], при этом для хранения информации о текущих фрагментах используется система непересекающихся множеств^[2] с общим временем работы [math]O(m \alpha(m, n))[/math]. Итоговая сложность алгоритма [math]O(m \ln n)[/math].

Как видно, наибольшую сложность имеет этап сортировки, при этом большая часть рёбер сортируется напрасно: они всё равно будут отброшены, как принадлежащие одному фрагменту. Использование инкрементальной быстрой сортировки^[3] (англ. IQS: Incremental Quick Sort) позволяет снизить затраты на сортировку, так что среднее время работы алгоритма составляет [math]O(m + n \ln^2 n)[/math].

В случае, если рёбра графа изначально отсортированы по весу рёбер, сложность алгоритма снижается до [math]O(m \alpha(m, n))[/math].

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

Основная часть алгоритма Крускала является последовательной, так как рёбра рассматриваются в порядке возрастания веса строго одно за другим. На начальном этапе может быть применена параллельная быстрая сортировка для упорядочения рёбер по весу.

Следующее свойство позволяет использовать алгоритм Крускала для организации параллельного или распределённого вычисления минимального остовного дерева.

Ассоциативность по рёбрам. Пусть [math]MSF(E)[/math] – минимальный остовный лес графа с рёбрами [math]E[/math]. Тогда

[math] MSF(E_1 \cup E_2 \cup \dots \cup E_k) = MSF(MSF(E_1) \cup MSF(E_2) \cup \dots \cup MSF(E_k)). [/math]

Параллельная схема вычисления устроена следующим образом. Рёбра графа распределяются между процессами примерно поровну. Каждый процесс строит минимальный остовный лес из своих рёбер, используя алгоритм Крускала. После этого процессы выполняют коллективную операцию редукции по приведённой формуле, используя алгоритм Крускала без сортировки рёбер, так как построенные ранее деревья уже записаны в порядке возрастания весов рёбер.

1.9 Входные и выходные данные алгоритма

1.10 Свойства алгоритма

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Возможные способы и особенности параллельной реализации алгоритма

2.3 Результаты прогонов

2.4 Выводы для классов архитектур

3 Литература

↑ 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.

[1] 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.

[2] 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.

[3] 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.

[1]

[2]

[3]

@@ Строка 1: / Строка 1: @@
-== Свойства и структура алгоритмов ==
+{{level-a}}
+== Свойства и структура алгоритма ==
 === Общее описание алгоритма ===
@@ Строка 6: / Строка 8: @@
 В отличие от алгоритмов [[Алгоритм Прима|Прима]] и [[Алгоритм Борувки|Борувки]], алгоритм Крускала не требует информации о рёбрах конкретной вершины, вместо этого на его вход подаётся общий список рёбер графа в произвольном порядке. Кроме этого, каждое (ненаправленное) ребро достаточно представить лишь одной из его направленных дуг, что на практике означает в два раза меньший объём вычислений. Последовательная версия алгоритма Крускала работает, как правило, быстрее последовательной версии алгоритма Борувки, а при условии предварительной сортировки списка рёбер по весу сложность алгоритма снижается до <math>O(m \alpha(m, n))</math>.
-=== Математическое описание ===
+=== Математическое описание алгоритма ===
 Пусть задан связный неориентированный граф <math>G = (V, E)</math> с весами рёбер <math>f(e)</math>. Предполагается, что веса всех рёбер различны (если это не так, то можно упорядочить рёбра сначала по весу, а потом по номеру).
@@ Строка 18: / Строка 20: @@
 === Вычислительное ядро алгоритма ===
 === Макроструктура алгоритма ===
-=== Описание схемы реализации последовательного алгоритма ===
+=== Схема реализации последовательного алгоритма ===
 === Последовательная сложность алгоритма ===
@@ Строка 28: / Строка 30: @@
 === Информационный граф ===
-=== Описание ресурса параллелизма алгоритма ===
+=== Ресурс параллелизма алгоритма ===
+Основная часть алгоритма Крускала является последовательной, так как рёбра рассматриваются в порядке возрастания веса строго одно за другим. На начальном этапе может быть применена параллельная быстрая сортировка для упорядочения рёбер по весу.
+Следующее свойство позволяет использовать алгоритм Крускала для организации параллельного или распределённого вычисления минимального остовного дерева.
-Пусть задан связный неориентированный граф <math>G = (V, E)</math> с весами рёбер <math>f(e)</math>. Предполагается, что веса всех рёбер различны (если это не так, то можно упорядочить рёбра сначала по весу, а потом по номеру).
+'''Ассоциативность по рёбрам'''. Пусть <math>MSF(E)</math> – минимальный остовный лес графа с рёбрами <math>E</math>. Тогда
+:<math>
+        MSF(E_1 \cup E_2 \cup \dots \cup E_k) = MSF(MSF(E_1) \cup MSF(E_2) \cup \dots \cup MSF(E_k)).
+</math>
-Алгоритм Борувки основан на следующих двух свойствах задачи:
+Параллельная схема вычисления устроена следующим образом. Рёбра графа распределяются между процессами примерно поровну. Каждый процесс строит минимальный остовный лес из своих рёбер, используя алгоритм Крускала. После этого процессы выполняют коллективную операцию редукции по приведённой формуле, используя алгоритм Крускала без сортировки рёбер, так как построенные ранее деревья уже записаны в порядке возрастания весов рёбер.
-* '''Минимальное ребро фрагмента'''. Пусть <math>F</math> – фрагмент минимального остовного дерева и <math>e_F</math> – ребро наименьшего веса, исходящее из <math>F</math> (т.е. ровно один его конец является вершиной из <math>F</math>). Если ребро <math>e_F</math> единственно, то оно принадлежит минимальному остовному дереву.
-* '''Схлопывание фрагментов'''. Пусть <math>F</math> – фрагмент минимального остовного дерева графа <math>G</math>, а граф <math>G'</math> получен из <math>G</math> склеиванием вершин, принадлежащих <math>F</math>. Тогда объединение <math>F</math> и минимального остовного дерева графа <math>G'</math> даёт минимальное остовное дерево исходного графа <math>G</math>.
-В начале работы алгоритма каждая вершина графа <math>G</math> является отдельным фрагментом. На очередном шаге у каждого фрагмента выбирается исходящее ребро минимального веса (если такое ребро существует). Выбранные рёбра добавляются в минимальное остовное дерево, а соответствующие фрагменты склеиваются.
+=== Входные и выходные данные алгоритма ===
+=== Свойства алгоритма ===
-=== Описание входных и выходных данных ===
+== Программная реализация алгоритма ==
-=== Свойства алгоритма===
-== Программная реализация алгоритмов ==
 === Особенности реализации последовательного алгоритма ===
-=== Описание локальности данных и вычислений ===
+=== Возможные способы и особенности параллельной реализации алгоритма ===
-=== Возможные способы и особенности реализации параллельного алгоритма ===
+=== Результаты прогонов ===
-=== Масштабируемость алгоритма и его реализации ===
-=== Динамические характеристики и эффективность реализации алгоритма ===
 === Выводы для классов архитектур ===
-=== Существующие реализации алгоритма ===
-* C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/kruskal_min_spanning_tree.html kruskal_min_spanning_tree]</code>), сложность <math>O(m \ln m)</math>.
-* 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#merge-local-minimum-spanning-trees merge_local_minimum_spanning_trees]</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>).
-* Java: [http://jgrapht.org JGraphT] (класс <code>[http://jgrapht.org/javadoc/org/jgrapht/alg/KruskalMinimumSpanningTree.html KruskalMinimumSpanningTree]</code>).
 == Литература ==
 <references />
+[[Категория:Начатые статьи]]
+[[en:Kruskal's algorithm]]