Алгоритм Краскала — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Реализация)
Строка 10: Строка 10:
 
1) <tex>F := (V, \varnothing)</tex><br>
 
1) <tex>F := (V, \varnothing)</tex><br>
 
1) Отсортируем <tex>E</tex> по весу ребер.<br>
 
1) Отсортируем <tex>E</tex> по весу ребер.<br>
2) Заведем систему непересекающихся множеств (DSU) и инициализируем ее множеством <tex>V</tex>. Каждая вершина находится в своем дереве.<br>
+
2) Заведем систему непересекающихся множеств (DSU) и инициализируем ее множеством <tex>V</tex>.<br>
3) Перебирая ребра <tex>uv \in EG</tex> в порядке увеличения веса, смотрим, принадлежат ли его концы разным деревьям. Если да, то сливаем эти деревья в DSU и добавляем ребро <tex>uv</tex> к <tex>F</tex>.<br>
+
3) Перебирая ребра <tex>uv \in EG</tex> в порядке увеличения веса, смотрим, принадлежат ли <tex>u</tex> и <tex>v</tex> одному множеству. Если нет, то сливаем множества, в которых лежат <tex>u</tex> и <tex>v</tex>, в DSU и добавляем ребро <tex>uv</tex> к <tex>F</tex>.<br>
  
 
==Асимптотика==
 
==Асимптотика==

Версия 06:43, 22 декабря 2011

Алгоритм Краскала - алгоритм поиска минимального остовного дерева (minimum spanning tree, MST) во взвешенном неориентированном связном графе.

Идея

Будем последовательно строить подграф [math]F[/math] графа [math]G[/math] ("растущий лес"), поддерживая следующий инвариант: на каждом шаге [math]F[/math] можно достроить до некоторого MST. Начнем с того, что включим в [math]F[/math] все вершины графа [math]G[/math]. Теперь будем обходить множество [math]EG[/math] в порядке увеличения веса ребер. Добавление очередного ребра [math]e[/math] в [math]F[/math] может привести к возникновению цикла в одной из компонент связности [math]F[/math]. В этом случае, очевидно, [math]e[/math] не может быть включено в [math]F[/math]. В противном случае [math]e[/math] соединяет разные компоненты связности [math]F[/math] и из леммы о безопасном ребре следует, что [math]F+e[/math] можно продолжить до MST, поэтому добавим это ребро в [math]F[/math].
Из леммы о безопасном ребре следует, что [math]F[/math] - MST.

Реализация

Вход: граф [math]G = (V, E)[/math]
Выход: минимальный остов [math]F[/math] графа [math]G[/math]
1) [math]F := (V, \varnothing)[/math]
1) Отсортируем [math]E[/math] по весу ребер.
2) Заведем систему непересекающихся множеств (DSU) и инициализируем ее множеством [math]V[/math].
3) Перебирая ребра [math]uv \in EG[/math] в порядке увеличения веса, смотрим, принадлежат ли [math]u[/math] и [math]v[/math] одному множеству. Если нет, то сливаем множества, в которых лежат [math]u[/math] и [math]v[/math], в DSU и добавляем ребро [math]uv[/math] к [math]F[/math].

Асимптотика

Сортировка [math]E[/math] займет [math]O(E\log E)[/math].
Работа с DSU займет [math]O(E\alpha(V))[/math], где [math]\alpha[/math] - обратная функция Аккермана, которая не превосходит 4 во всех практических приложениях и которую можно принять за константу.
Алгоритм работает за [math]O(E(\log E+\alpha(V))) = O(E\log E) = O(E\log V^2) = O(E\log V)[/math].

Литература

  • Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

См. также