Изменения
Нет описания правки
Работа с DSU займет <tex>O(E\alpha(V))</tex>, где <tex>\alpha</tex> - обратная функция Аккермана, которая не превосходит 4 во всех практических приложениях и которую можно принять за константу.<br>
Алгоритм работает за <tex>O(E(\log E+\alpha(V))) = O(E\log E) = O(E\log V^2) = O(E\log V)</tex>.
==См. также==
* [[Алгоритм Прима]]
* [[Алгоритм Борувки]]
==Источники информации==
* Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд — Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D1%80%D1%83%D1%81%D0%BA%D0%B0%D0%BB%D0%B0 Википедия - Алгоритм Крускала]
* [http://en.wikipedia.org/wiki/Kruskal's_algorithm Wikipedia - Kruskal's algorithm]
* [http://e-maxx.ru/algo/mst_kruskal MAXimal :: algo :: Минимальное остовное дерево. Алгоритм Крускала]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]
