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

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

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

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

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

Математическое описание

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

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

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

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

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

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

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

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

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

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

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