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