Главная → Проекты → Реализация алгоритма Краскала

Реализация алгоритма    КРАСКАЛА:             

 Вход: список Е ребер графа G с длинами. 
 Выход: множество Т ребер кратчайшего остова.
 Т:=пуст.мн-во 
 упорядочить Е в порядке возрастания длин 
 k: = 1 { номер рассматриваемого ребра } 
 for i from 1 to p - 1 do 
 while добавление ребра E(k) образует цикл в T do 
 k: = k + 1 { пропустить это ребро } 
 end while
 T: = T U {E[k]} { добавить это ребро в SST }
 end for 

 

Скачать программу и исходники

Другие материалы:

• Реализация алгоритма Дейкстры

Метки: Краскал, алгоритмы.

Комментарии: