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