Изменения

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

Алгоритм Борувки

60 байт убрано, 02:03, 15 декабря 2012
Реализация
Graph Boruvka(Graph G)
while T.size < n
for u <tex>\in</tex> G init() color[u] = 0 minEdge[u] = MAX_EDGE / findComp(T) /MAX_EDGE ребро весом бесконечности for u <tex>\in</tex> G if !u.color разбивает граф T на компоненты связынности обычным dfs(u, color++)-ом
for uv <tex>\in</tex> E
if u.color != v.color
if minEdge[u.componentcomp].w < uv.w minEdge[u.componentcomp] = uv if minEdge[v.componentcomp].w < uv.w minEdge[v.componentcomp] = uv) for k <tex>\in</tex> K// K - множество компонент связанности в T
T.addEdge(minEdge[k])
394
правки

Навигация