Алгоритм Прима усовершенствованный

1 , где a – произвольная вершина графа;

2 for do ;

3 while do

4 найти вершину с наименьшим значением ;

5 добавить к U вершину y;

6 for do if then .

При цикл в строке 6 повторяется раз. Таким образом, дополнительное время, необходимое для обслуживания массива f,тоже оценивается сверху квадратичной функцией от n и общая оценка трудоемкости усовершенствованного алгоритма Прима будет .