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

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

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

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