Изменения

<b>Алгоритм Краскала</b> (англ. ''Kruskal's algorithm'') — алгоритм поиска [[Лемма о безопасном ребре#Необходимые определения | минимального остовного дерева ]] (англ. ''minimum spanning tree'', ''MST'') во взвешенном [[Основные определения теории графов#Неориентированные графы | неориентированном связном графе]].

Будем последовательно строить подграф <tex>F</tex> графа <tex>G</tex> ("растущий лес"), поддерживая следующий инвариант: пытаясь на каждом шаге достроить <tex>F</tex> можно достроить до некоторого MST. Начнем с того, что включим в <tex>F</tex> все вершины графа <tex>G</tex>. Теперь будем обходить множество <tex>EGE(G)</tex> в порядке увеличения веса неубывания весов ребер. Добавление очередного ребра Если очередное ребро <tex>e</tex> в соединяет вершины одной компоненты связности <tex>F</tex> может привести , то добавление его в остов приведет к возникновению цикла в одной из компонент этой компоненте связности <tex>F</tex>. В этом таком случае, очевидно, <tex>e</tex> не может быть включено в <tex>F</tex>. В противном случае Иначе <tex>e</tex> соединяет разные компоненты связности <tex>F</tex>, тогда существует [[Лемма о безопасном ребре#Необходимые определения|разрез]] <tex> \langle S, T \rangle </tex> [[Лемма о безопасном ребре#Необходимые определения|разрез]] такой, что одна из компонент связности составляет одну его часть, а оставшаяся часть графа - — вторую. Тогда <tex>e</tex> - единственное — минимальное ребро между частями разреза, которое и будет минимальнымпересекающее этот разрез. Значит , из [[Лемма о безопасном ребре#Лемма о безопасном ребре|леммы о безопасном ребре]] следует, что <tex>F+e</tex> можно продолжить до MSTявляется безопасным, поэтому добавим это ребро в <tex>F</tex>.На последнем шаге ребро соединит две оставшиеся компоненты связности, полученный подграф будет минимальным остовным деревом графа <brtex>G</tex>.Несложно понять, что после выполнения такой процедуры получится остовное дерево, при этом его минимальность вытекает из леммы о безопасном ребреДля проверки возможности добавления ребра используется [[СНМ (реализация с помощью леса корневых деревьев) | система непересекающихся множеств]].

<bfont color=green>// <tex>G</tex> {{---}} исходный граф</font> <font color=green>// <tex>F</tex>Вход{{---}} минимальный остов</bfont> '''function''' <tex>\mathtt{kruskalFindMST}(): граф </tex> <tex>\mathtt{F} \leftarrow V(G = )</tex> <tex>\mathtt{sort}(V, E(G))\</tex> '''for''' <brtex>vu \in E(G)</tex> '''if''' <btex>Выходv</btex>: минимальный остов и <tex>Fu</tex> графа в разных компонентах связности <tex>GF</tex> <tex> \mathtt{F}\ =\ \mathtt{F} \bigcup vu\<br/tex>1) '''return''' <tex>\mathtt{F :} </tex> ==Задача о максимальном ребре минимального веса== Легко показать, что максимальное ребро в MST минимально. Обратное в общем случае неверно. Но MST из-за сортировки строится за <tex>O(V, E \varnothinglog E)</tex><br>. Однако из-за того, что необходимо минимизировать только максимальное ребро, а не сумму всех рёбер, можно предъявить алгоритм, решающий задачу за линейное время. 1) Отсортируем С помощью [[Поиск_k-ой_порядковой_статистики_за_линейное_время | алгоритма поиска k-ой порядковой статистики]] найдем ребро-медиану за <tex>O(E)</tex> и разделим множество ребер на два равных по мощности так, чтобы ребра в первом не превосходили по весу реберво втором. Проверим образуют ли ребра из первого подмножества остов графа, запустив [[Использование_обхода_в_глубину_для_проверки_связности|обход в глубину]].* Если да, то рекурсивно запустим алгоритм от него.* В противном случае сконденсируем получившиеся несвязные компоненты в супервершины и рассмотрим граф с этими вершинами и ребрами из второго подмножества.На последнем шаге останутся две компоненты связности и одно ребро в первом подмножестве — это максимальное ребро минимального веса. На каждом шаге ребер становится в два раза меньше, а все операции выполняются за время пропорциональное количеству ребер на текущем шаге, тогда время работы алгоритма <brtex>O(E+\frac{E}{2}+\frac{E}{4}+...+1) Заведем систему непересекающихся множеств =O(E)</tex>. ==Пример=={| class = "wikitable"| Рёбра ''(DSUв порядке их просмотра) и инициализируем ее множеством '' || ae || cd || ab || be || bc || ec || ed|-| Веса рёбер ||<tex>1</tex> || <tex>V2</tex>.|| <brtex>3) Перебирая ребра </tex> || <tex>4</tex> || <tex>uv \in EG5</tex> в порядке увеличения веса, смотрим, принадлежат ли || <tex>u6</tex> и || <tex>v7</tex> одному множеству|} {| class = "wikitable"! Изображение !! Описание|-|[[Файл:Mst_kruskal_1. Если нетpng|200px]]|style="padding-left: 1em" |Первое ребро, которое будет рассмотрено — '''ae''', то объединяем множестватак как его вес минимальный.<br/>Добавим его к ответу, так как его концы соединяют вершины из разных множеств ('''a''' — красное и '''e''' — зелёное).<br/>Объединим красное и зелёное множество в которых лежат одно (красное), так как теперь они соединены ребром.|-|[[Файл:Mst_kruskal_2.png|200px]]|style="padding-left: 1em" |Рассмотрим следующие ребро — '''cd'''.<texbr/>uДобавим его к ответу, так как его концы соединяют вершины из разных множеств ('''c''' — синее и '''d''' — голубое).<br/tex> Объединим синее и голубое множество в одно (синее), так как теперь они соединены ребром.|-|[[Файл:Mst_kruskal_3.png|200px]]|style="padding-left: 1em" |Дальше рассмотрим ребро '''ab'''.<texbr/>vДобавим его к ответу, так как его концы соединяют вершины из разных множеств ('''a''' — красное и '''b''' — розовое).<br/tex>Объединим красное и розовое множество в одно (красное), и добавляем так как теперь они соединены ребром.|-|[[Файл:Mst_kruskal_4.png|200px]]|style="padding-left: 1em" |Рассмотрим следующие ребро — '''be'''.<texbr/>uvОно соединяет вершины из одного множества, поэтому перейдём к следующему ребру '''bc'''<br/tex> Добавим его к ответу, так как его концы соединяют вершины из разных множеств ('''b''' — красное и '''c''' — синее).<texbr/>Объединим красное и синее множество в одно (красное), так как теперь они соединены ребром.|-|[[Файл:Mst_kruskal_5.png|200px]]|style="padding-left: 1em" |Рёбра '''ec''' и '''ed''' соединяют вершины из одного множества,<br/>Fпоэтому после их просмотра они не будут добавлены в ответ<br/tex>Всё рёбра были рассмотрены, поэтому алгоритм завершает работу.<br/>Полученный граф — минимальное остовное дерево|}

Работа с DSU СНМ займет <tex>O(E\alpha(V))</tex>, где <tex>\alpha</tex> - — обратная функция Аккермана, которая не превосходит <tex>4 </tex> во всех практических приложениях и которую можно принять за константу.<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 (рус.)

[[Категория: Остовные деревья ]][[Категория: Построение остовных деревьев]]