Алгоритм Краскала

Задача отыскания кратчайшего остова графа является классической задачей теории графов. Методы решения этой задачи послужили основой для многих других важных результатов. Задача о нахождении кратчайшего остова принадлежит к числу немногих задач теории графов, которые можно считать полностью решенными. Между тем, если изменить условия задачи, на первый взгляд даже незначительно, то она оказывается значительно более трудной.

Алгоритм строит остов:

Вход: граф , заданный матрицей длин рёбер .

Выход: остов .

while в больше одного элемента do

взять любое поддерево из

найти к нему ближайшее

соединить эти деревья в

end while

В частности, исследования алгоритма Краскала привели в конечном счете к теории жадных алгоритмов. Следующий жадный алгоритм, известный как алгоритм Краскала, находит кратчайший остов в связном графе.