212
правок
Изменения
м
→Реализация
'''function''' <tex>\mathtt{boruvkaMST}():</tex>
'''while''' <tex>T\mathtt{.size} < n - 1</tex>
'''for''' <tex>k \in </tex> Component <font color = "green">// Component — {{---}} множество компонент связности в <tex>T</tex>. Для </font> <tex>w(\mathtt{minEdge}[k])=\infty</tex> <font color = "green">// для каждой компоненты связности вес минимального ребра = <tex>\infty</tex>.</font> <tex>\mathtt{findComp(}T\mathtt{)}</tex> <font color = "green">// разбиваем Разбиваем граф <tex>T</tex> на компоненты связности обычным ''dfs''-ом.</font>
'''for''' <tex>\mathtt{(u,v)} \in E </tex>
'''if''' <tex>\mathtt{u.comp} \neq \mathtt{v.comp}</tex>
<tex>\mathtt{minEdge}[\mathtt{v.comp}] = (u,v)</tex>
'''for''' <tex>k \in </tex> Component
<tex>T\mathtt{.addEdge}(\mathtt{minEdge}[k])</tex> <font color = "green">// добавляем ребро , если его не было в <tex>T</tex></font>
'''return''' <tex>T</tex>
|}
