Алгоритм Крускала

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.6 Последовательная сложность алгоритма

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

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

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

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]

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

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

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

• C++: Boost Graph Library (функция kruskal_min_spanning_tree), сложность [math]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).