Алгоритм Борувки: различия между версиями

'''Алгоритм Борувки''' (''Borůvka's algorithm'') --- алгоритм поиска [[Каркас|каркаса]] наименьшего веса во [[Взвешенный граф|взвешенном]] неориентированном [[Связный граф|связном]] графе. Впервые был опубликован в 1926 году Отакаром Борувкой.

Алгоритм начинает с рассмотрения исходного графа, как множества [[Тривиальный граф|тривиальных]] деревьев (по числу вершин исходного графа), и затем до тех пор, пока не останется только одно дерево (оно и есть результат работы алгоритма), для каждого дерева находит минимальное по весу инцидентное ему ребро и добавляет все такие ребра.  

Алгоритм может работать неправильно, если в графе есть равные по весу ребра, которые образуют треугольник, и нуждается в модификации.