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

Задача

Дан неориентированный взвешенный граф $G=(V, E)$.

Остовным деревом в $G$ называется граф $ST=(V, E')$ такой что $E' \subset E$ и $ST$ является деревом. Говоря простым языком, мы оставляем в графе только некоторые рёбра, чтобы оставшийся граф был деревом (или, ещё говорят, скелетом).

Весом графа мы будем называть суммарный вес всех рёбер, входящих в него.

Наша задача состоит в том, чтобы найти MST $~-$ Minimal Spanning Tree $~-$ остовное дерево минимального веса.

Замечание

В графе может быть много минимальных остовных деревьев. Например, в полном графе на $n$ вершинах, с весами всех рёбер, равных $1$, их $n^{n-2}$.

Как и Алгоритм Прима, алгоритм Краскала основывается на лемме о безопасном ребре.

Алгоритм

• Будем строить итоговое остовное дерево, объединяя деревья в большие, пока не получим дерево, состоящее из всех вершин графа.
• Изначально все деревья состоят из одной вершины.

• Отсортируем все рёбра в графе по неубыванию веса.
• Начнём перебирать рёбра в порядке неубывания веса.
  • Если текущее ребро $(u, v)$ соединяет вершины из разных деревьев, то по лемме о безопасном ребре $(u, v)$ можно добавить в миностов. Для этого нам надо провести ребро между вершинами $u$ и $v$ и объединить их деревья в одно.
  • Если текущее ребро соединяет вершины одного и того же дерева, то пропускаем его.

Алгоритм заканчивается в тот момент, когда все вершины окажутся в одном дереве.

Корректность алгоритма

Корректность следует из леммы о безопасном ребре.

Как работать с компонентами

Будем поддерживать деревья с помощью СНМ. Действительно, чтобы провести проверить, что ребро $(u, v)$ соединяет вершины из разных деревьев, достаточно убедиться, что $GetRoot(u) \neq GetRoot(v)$. А для того, чтобы затем объединить два дерева в одно, достаточно выполнить $Merge(u, v)$.

Асимптотика

Итоговая сложность алгоритма составляет $$ O(\underbrace{E \times \log(E)}_\text{сортировка рёбер по неубыванию веса} + \underbrace{E \times \log^{*}(V)}_\text{для каждого ребра мы 2 раза вызываем $GetRoot$ и, иногда, $Merge$} = O(E \times \log(E)) $$

---

Автор конспекта: Александр Гришутин

По всем вопросам пишите в telegram @rationalex