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

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

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