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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 7: Строка 7:
  
 
=== Математическое описание ===
 
=== Математическое описание ===
 +
 +
Пусть задан связный неориентированный граф <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> является отдельным фрагментом. На каждом шаге из рёбер, ещё не рассмотренных на предыдущих шагах, выбирается ребро с минимальным весом. Если оно соединяет два различных фрагмента, то оно добавляется в минимальное опорное дерево, а фрагменты склеиваются. В противном случае это ребро отбрасывается.
 +
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===
 
=== Макроструктура алгоритма ===
 
=== Макроструктура алгоритма ===

Версия 15:49, 8 июля 2015

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 Описание ресурса параллелизма алгоритма

1.9 Описание входных и выходных данных

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

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

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

2.2 Описание локальности данных и вычислений

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

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

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

2.7 Существующие реализации алгоритма

3 Литература

  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.