Изменения
Нет описания правки
==Идея==
Будем последовательно строить подграф <tex>F</tex> графа <tex>G</tex> ("растущий лес"), поддерживая следующий инвариант: на каждом шаге <tex>F</tex> можно достроить до некоторого MST. Начнем с того, что включим в <tex>F</tex> все вершины графа <tex>G</tex>. Теперь будем обходить множество <tex>EG</tex> в порядке увеличения веса ребер. Добавление очередного ребра <tex>e</tex> в <tex>F</tex> может привести к возникновению цикла в одной из компонент связности <tex>F</tex>. В этом случае, очевидно, <tex>e</tex> не может быть включено в <tex>F</tex>. В противном случае <tex>e</tex> соединяет разные компоненты связности <tex>F</tex> и из [[Лемма о безопасном ребре|леммы о безопасном ребре]] следует, что <tex>F+e</tex> можно продолжить до MST, поэтому добавим это ребро в <tex>F</tex>.<br>
Из связности <tex>G</tex> следует, что в конце алгоритма <tex>F</tex> будет связным, а способ построения <tex>F</tex> гарантирует его ацикличность. Это означает, что получилось остовное дерево. Пусть оно не минимально, но тогда на последнем шаге алгоритма нарушилась лемма леммы о безопасном ребре. Таким образомследует, что <tex>F</tex> - MST.
==Реализация==
1) Отсортируем <tex>E</tex> по весу ребер.<br>
2) Заведем систему непересекающихся множеств (DSU) и инициализируем ее множеством <tex>V</tex>.<br>
3) Перебирая ребра <tex>uv \in EG</tex> в порядке увеличения веса, смотрим, одинакового ли представителя для <tex>u</tex> и <tex>v</tex> возвращает DSU. Если нет, то делаем слияние этих представителей множеств в DSU и полагаем <tex>F := F + uv</tex>.<br>
==Асимптотика==
