Изменения

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

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

123 байта добавлено, 23:06, 19 ноября 2014
Реализация
<font color=green>// <tex>G</tex> {{---}} исходный граф</font>
<font color=green>// <tex>F</tex> {{---}} минимальный остов</font>
<font color=green>// для проверки возможности добавления ребра используется система непересекающихся множеств</font>
'''function''' <tex>\mathtt{kruskalFindMST}():</tex>
<tex> \mathtt{F}\ =\ \varnothing </tex>
'''for''' <tex>v \in V(G)</tex>
<tex>\mathtt{makeSet}(v)\</tex>
<tex>\mathtt{sort}(E(G))\</tex>
'''for''' <tex>vu \in E(G)</tex>
'''if''' <tex>\mathtt{findSet}(v)\ \ne \mathtt{findSet}(</tex> и <tex>u)</tex> в разных компонентах связности <tex>F</tex>
<tex> \mathtt{F}\ =\ \mathtt{F} \bigcup \mathtt{vu}\</tex>
<tex>\mathtt{Unite}(v, u)\ </tex>
==Задача о максимальном ребре минимального веса==
Анонимный участник

Навигация