Изменения

Перейти к: навигация, поиск

Алгоритм Краскала

178 байт убрано, 23:25, 3 ноября 2014
Реализация
==Реализация==
<bfont color=green>Вход</b>: граф / <tex>G = (V, E)</tex>{{---}} исходный граф<br/font> <bfont color=green>Выход</b>: минимальный остов / <tex>F</tex> графа <tex>G{{---}} минимальный остов</tex><brfont>1) '''function''' <tex>F := \mathtt{kruskalFindMST}(V, \varnothing):</tex><br>1) Отсортируем <tex>E\mathtt{F}\ =\ \varnothing </tex> по весу ребер.<br>2) Заведем систему непересекающихся множеств (DSU) и инициализируем ее множеством '''for''' <tex>v \in V(G)</tex>.<br>3) Перебирая ребра <tex>uv \in EGmathtt{makeSet}(v)\</tex> в порядке увеличения веса, смотрим, принадлежат ли <tex>u\mathtt{sort}(E(G))\</tex> и '''for''' <tex>vvu \in E(G)</tex> одному множеству. Если нет, то объединяем множества, в которых лежат отсортированном порядке '''if''' <tex>\mathtt{findSet}(u</tex> и <tex>)\ \ne \mathtt{findSet}(v)</tex>, и добавляем ребро <tex>uv\mathtt{F}\ =\ \mathtt{F}\ \bigcup \mathtt{vu}\</tex> к <tex>F\mathtt{Union}(v, u)\ </tex>.<br>
==Пример==
Анонимный участник

Навигация