Изменения

int res = 0

int minEdge[n] // создаем массив минимумов, входящих в каждую компоненту, инициализируем бесконечностью.

minEdge[e.to] = min(e.w, minEdge[e.to])

for each <tex>v \in V \backslash \{root\}</tex>

res += minEdge[v] //веса минимальных ребер точно будут в результате

edge zeroEdges[] //создаем массив нулевых ребер

if e.w == minEdge[e.to]

zeroEdges.pushback(<tex>e_1</tex>) // <tex>e_1</tex> - ребро е, уменьшенное на минимальный вес, входящий в e.to

for each <tex>e \in</tex> edges

if e.to и e.from в разных компонентах

res += findMST(newEdges, ComponentsCount, newComponents[root])

return res

==См. также==

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

* [http://rain.ifmo.ru/cat/view.php/vis/graph-spanning-trees/shortest-tree-chinese-2003 Визуализатор алгоритма]

[[Категория: Алгоритмы и структуры данных]]

[[Категория: Остовные деревья ]]