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

Алгоритм Краскала — это жадный алгоритм в теории графов, предназначенный для нахождения минимального остовного дерева (МОД) во взвешенном неориентированном связном графе. Алгоритм последовательно добавляет рёбра в порядке возрастания их весов, избегая образования циклов, что гарантирует построение остова с минимальной суммарной массой. Назван в честь американского математика Джозефа Краскала, впервые опубликовавшего алгоритм в 1956 году.

История

Алгоритм был предложен Джозефом Краскалом (Joseph Kruskal, 1928–2010) в статье «On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem», опубликованной в журнале Proceedings of the American Mathematical Society в 1956 году. Работа Краскала стала одним из первых систематических методов решения задачи о минимальном остовном дереве, которая до этого решалась эвристически. Примерно в то же время чешский математик Войтех Ярник (1929) и голландский учёный Эдсгер Дейкстра (1959) предложили альтернативный алгоритм Прима, решающий ту же задачу, но иным способом. Алгоритм Краскала остаётся одним из фундаментальных алгоритмов дискретной математики и широко применяется в компьютерных науках, проектировании сетей и кластерном анализе.

Постановка задачи

Дано: связный неориентированный граф \( G = (V, E) \), где \( V \) — множество вершин, \( E \) — множество рёбер, каждому ребру \( e \in E \) приписан положительный вес \( w(e) \). Требуется найти остовное дерево \( T \subseteq E \), соединяющее все вершины \( V \), такое, что сумма весов рёбер \( \sum_{e \in T} w(e) \) минимальна. Остовное дерево — это подграф, не содержащий циклов и содержащий ровно \( |V| - 1 \) ребро.

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

Алгоритм Краскала работает по следующей схеме:

Сортировка рёбер. Все рёбра графа сортируются в порядке неубывания весов.
Инициализация. Создаётся пустое множество рёбер будущего остовного дерева \( T \). Каждая вершина графа помещается в отдельное подмножество (компоненту связности).
Последовательный просмотр. Для каждого ребра в отсортированном списке (от наименьшего веса к наибольшему) проверяется, соединяет ли оно две вершины из разных компонент связности. Если да, то ребро добавляется в \( T \), и компоненты объединяются. Если нет (ребро образует цикл), оно отбрасывается.
Завершение. Алгоритм останавливается, когда в \( T \) набрано \( |V| - 1 \) ребро, или когда все рёбра просмотрены.

Пример работы

Рассмотрим граф с вершинами A, B, C, D и рёбрами: AB (1), AC (3), AD (4), BC (2), BD (5), CD (6). Сортировка рёбер по весу: AB (1), BC (2), AC (3), AD (4), BD (5), CD (6).

Добавляем AB (1). Компоненты: {A,B}, {C}, {D}.
Добавляем BC (2). Соединяет {A,B} и {C} → {A,B,C}, {D}.
Рассматриваем AC (3). Обе вершины в одной компоненте {A,B,C} — отбрасываем.
Добавляем AD (4). Соединяет {A,B,C} и {D} → {A,B,C,D}. Получено 3 ребра (|V|-1=3). Остовное дерево: AB, BC, AD. Суммарный вес: 1+2+4=7.

Реализация

Для эффективной реализации алгоритма Краскала требуется структура данных для поддержания непересекающихся множеств (Disjoint Set Union, DSU), которая позволяет быстро выполнять две операции:

Find — определение, какой компоненте принадлежит вершина.
Union — объединение двух компонент.

Псевдокод на языке, близком к Python:

```python def kruskal(vertices, edges):

edges: список кортежей (вес, u, v)

edges.sort(key=lambda x: x[0]) # сортировка по весу parent = {v: v for v in vertices} rank = {v: 0 for v in vertices}

def find(v): while parent[v] != v: parent[v] = parent[parent[v]] v = parent[v] return v

def union(u, v): ru, rv = find(u), find(v) if ru == rv: return False if rank[ru] < rank[rv]: parent[ru] = rv elif rank[ru] > rank[rv]: parent[rv] = ru else: parent[rv] = ru rank[ru] += 1 return True

mst = [] total_weight = 0 for weight, u, v in edges: if union(u, v): mst.append((u, v, weight)) total_weight += weight if len(mst) == len(vertices) - 1: break return mst, total_weight ```

Анализ сложности

Временная сложность: \( O(E \log E) \) или \( O(E \log V) \), где \( E \) — количество рёбер, \( V \) — количество вершин. Основное время тратится на сортировку рёбер. Операции DSU (с эвристиками сжатия пути и объединения по рангу) выполняются почти за константное время (обратная функция Аккермана).
Пространственная сложность: \( O(V + E) \) для хранения графа и структур данных.

Доказательство корректности

Корректность алгоритма Краскала основывается на свойстве разреза графа и лемме о безопасном ребре. Пусть на каждом шаге алгоритма \( T \) — множество уже выбранных рёбер. Рассмотрим очередное ребро \( e \) минимального веса, соединяющее две разные компоненты связности. Существует разрез, разделяющий эти компоненты, и \( e \) — ребро минимального веса через этот разрез. Следовательно, \( e \) является безопасным для \( T \), и его добавление не нарушает возможность построения минимального остовного дерева. Алгоритм завершается, когда получено \( |V|-1 \) ребро, что гарантирует связность и ацикличность.

Варианты и модификации

Обратный алгоритм Краскала (reverse-delete algorithm): начинается с полного графа и удаляет рёбра в порядке убывания веса, если это не нарушает связность. Менее эффективен, но полезен для некоторых задач.
Алгоритм Борувки (1926) — исторически первый алгоритм для МОД, работающий за \( O(E \log V) \). Используется в параллельных вычислениях.
Алгоритм Прима — альтернативный жадный алгоритм, строящий дерево от одной вершины, также за \( O(E \log V) \) с использованием очереди с приоритетами.

Применение

Проектирование сетей: минимизация длины кабелей при соединении компьютеров, дорог, трубопроводов.
Кластерный анализ: построение минимального остовного дерева для выделения кластеров (например, алгоритм MST-кластеризации).
Компьютерное зрение: сегментация изображений на основе минимального остова.
Криптография: некоторые протоколы используют МОД для построения ключевых схем.
Транспортная логистика: оптимизация маршрутов доставки с минимальными затратами.

Интересные факты

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

Источники

Kruskal, J. B. (1956). "On the shortest spanning subtree of a graph and the traveling salesman problem". Proceedings of the American Mathematical Society, 7(1), 48–50.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press. Глава 23.
Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.
Ахо, А., Хопкрофт, Дж., Ульман, Дж. (2000). Структуры данных и алгоритмы. Вильямс.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →