Алгоритм Краскала. Задача отыскания кратчайшего остова графа является классической задачей теории графов

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

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

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

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

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

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

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

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

end while

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

Дата добавления: 2014-11-20