212
правок
Изменения
м
→Описание алгоритма
==Описание алгоритма==
# Построим граф <tex>T</tex>. Изначально <tex>T</tex> содержит все вершины из <tex>G</tex> и не содержит ребер (каждая вершина в графе <tex>T</tex> {{---}} отдельная компонента связности).
# Будем добавлять в <tex>T</tex> ребра следующим образом, пока <tex>T</tex> не является деревом#* Для каждой компоненты связности находим минимальное по весу ребро, которое связывает эту компоненту с другой. #* Добавим в <tex>T</tex> все найденные рёбра.# Получившийся граф Повторяем пункты <tex dpi = 120> 2 </tex> и <texdpi = 120>T3 </tex> является минимальным остовным деревом графа , пока граф <texdpi = 120>GT </tex>не станет деревом.
Данный алгоритм может работать неправильно, если в графе есть ребра равные по весу. Например, полный граф из трех вершин, вес каждого ребра равен один. В <tex>T</tex> могут быть добавлены все три ребра. Избежать эту проблему можно, выбирая в первом пункте среди ребер, равных по весу, ребро с наименьшим номером.
