234
правки
Изменения
→Реализация
=== Реализация ===
<br>
Проверяем, можно ли дойти из <tex>v</tex> до остальных вершин. Если можно - запускаем findMST. int findMST(edges, n, root)</tex>: int result = 0; int minEdge[n]; // создаем массив минимумов, входящих в каждую компоненту, инициализируем бесконечностью.
for each <tex>e \in E</tex>
minEdge[e.to] = min(e.w, minEdge[e.to])
for each <tex>v \in V, v != \backslash \{root\}</tex>
res += minEdge[v] //веса минимальных ребер точно будут в результате
edge zeroEdges[] //создаем массив нулевых ребер
for each <tex>e \in E</tex>
if (текущее ребро равно по весу минимальному, входящему в эту вершину)e.w == minEdge[e.to]
zeroEdges.pushback(<tex>e_1</tex>) // <tex>e_1</tex> - ребро е, уменьшенное на минимальный вес, входящий в e.to
return res
int newComponents[n]; // будущие компоненты связности newComponents = <tex>Сondensation(zeroEdges)</tex> edge newEdges[] //создаем массив ребер в новом графе с вершинами в сконденсированными компонентамиполученных компонентах
for each <tex>e \in</tex> zeroEdges
if (концы e лежат .to и e.from в разных компонентах связности)
добавляем в newEdges ребро с концами в данных компонентах и весом e.w
res += <tex>findMST(zeroEdges, ComponentsCount, newComponents[root])</tex>
return res
