Алгоритм Крускала: различия между версиями
| [непроверенная версия] | [досмотренная версия] |
Daryin (обсуждение | вклад) |
ASA (обсуждение | вклад) |
||
| (не показано 11 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
| − | == Свойства и структура | + | {{level-a}} |
| + | |||
| + | == Свойства и структура алгоритма == | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
| − | '''Алгоритм Крускала'''<ref>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.</ref> предназначен для решения [[Построение минимального остовного дерева (MST)|задачи о построении минимального остовного дерева]] во взвешенном неориентированном графе. В отличие от алгоритмов [[Алгоритм Прима|Прима]] и [[Алгоритм Борувки|Борувки]], алгоритм Крускала не требует информации о рёбрах конкретной вершины, вместо этого на его вход подаётся общий список рёбер графа в произвольном порядке. Кроме этого, каждое (ненаправленное) ребро достаточно представить лишь одной из его направленных дуг, что на практике означает в два раза меньший объём вычислений. Последовательная версия алгоритма Крускала работает, как правило, быстрее последовательной версии алгоритма Борувки, а при условии предварительной сортировки списка рёбер по весу сложность алгоритма снижается до <math>O(m \alpha(m, n))</math>. | + | '''Алгоритм Крускала'''<ref>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.</ref> предназначен для решения [[Построение минимального остовного дерева (MST)|задачи о построении минимального остовного дерева]] во взвешенном неориентированном графе. Последовательная сложность алгоритма <math>O(m \ln n)</math>. |
| + | |||
| + | В отличие от алгоритмов [[Алгоритм Прима|Прима]] и [[Алгоритм Борувки|Борувки]], алгоритм Крускала не требует информации о рёбрах конкретной вершины, вместо этого на его вход подаётся общий список рёбер графа в произвольном порядке. Кроме этого, каждое (ненаправленное) ребро достаточно представить лишь одной из его направленных дуг, что на практике означает в два раза меньший объём вычислений. Последовательная версия алгоритма Крускала работает, как правило, быстрее последовательной версии алгоритма Борувки, а при условии предварительной сортировки списка рёбер по весу сложность алгоритма снижается до <math>O(m \alpha(m, n))</math>. | ||
| + | |||
| + | === Математическое описание алгоритма === | ||
| + | |||
| + | Пусть задан связный неориентированный граф <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> является отдельным фрагментом. На каждом шаге из рёбер, ещё не рассмотренных на предыдущих шагах, выбирается ребро с минимальным весом. Если оно соединяет два различных фрагмента, то оно добавляется в минимальное остовное дерево, а фрагменты склеиваются. В противном случае это ребро отбрасывается. | ||
| − | |||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
| − | === | + | === Схема реализации последовательного алгоритма === |
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
| − | Время работы алгоритма складывается из сортировки рёбер и поддержания информации о фрагментах. В базовом варианте рёбра вначале сортируются за время <math>m \ln | + | Время работы алгоритма складывается из сортировки рёбер и поддержания информации о фрагментах. В базовом варианте рёбра вначале сортируются за время <math>m \ln n</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 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> (англ. IQS: Incremental Quick Sort) позволяет снизить затраты на сортировку, так что среднее время работы алгоритма составляет <math>O(m + n \ln^2 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> (англ. IQS: Incremental Quick Sort) позволяет снизить затраты на сортировку, так что среднее время работы алгоритма составляет <math>O(m + n \ln^2 n)</math>. | ||
| Строка 17: | Строка 30: | ||
=== Информационный граф === | === Информационный граф === | ||
| − | === | + | === Ресурс параллелизма алгоритма === |
| − | === | + | |
| − | === Свойства алгоритма=== | + | Основная часть алгоритма Крускала является последовательной, так как рёбра рассматриваются в порядке возрастания веса строго одно за другим. На начальном этапе может быть применена параллельная быстрая сортировка для упорядочения рёбер по весу. |
| − | == Программная реализация | + | |
| + | Следующее свойство позволяет использовать алгоритм Крускала для организации параллельного или распределённого вычисления минимального остовного дерева. | ||
| + | |||
| + | '''Ассоциативность по рёбрам'''. Пусть <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> | ||
| + | |||
| + | Параллельная схема вычисления устроена следующим образом. Рёбра графа распределяются между процессами примерно поровну. Каждый процесс строит минимальный остовный лес из своих рёбер, используя алгоритм Крускала. После этого процессы выполняют коллективную операцию редукции по приведённой формуле, используя алгоритм Крускала без сортировки рёбер, так как построенные ранее деревья уже записаны в порядке возрастания весов рёбер. | ||
| + | |||
| + | === Входные и выходные данные алгоритма === | ||
| + | === Свойства алгоритма === | ||
| + | |||
| + | == Программная реализация алгоритма == | ||
=== Особенности реализации последовательного алгоритма === | === Особенности реализации последовательного алгоритма === | ||
| − | + | === Возможные способы и особенности параллельной реализации алгоритма === | |
| − | === Возможные способы и особенности реализации | + | === Результаты прогонов === |
| − | === | ||
| − | |||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== Литература == | == Литература == | ||
<references /> | <references /> | ||
| + | |||
| + | [[Категория:Начатые статьи]] | ||
| + | |||
| + | [[en:Kruskal's algorithm]] | ||
Текущая версия на 10:03, 6 июля 2022
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 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.
