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

Рис. 5.7 (а)

Рис. 5.7 (б)

Рис. 5.7 (в)

Рис. 5.7 (г)

Рис. 5.7 (д)

Рис. 5.7 (е)

 В результате машинного расчета решения будут выбраны элементы , , , ,  и суммарная длина ребер при этом равна 29 (см. рис. 5.7, а-е).

Выводы: Оба рассмотренных алгоритма позволяют при выполнении соот-ветствующих условий находить глобально-оптимальные или близкие к ним решения.

При этом для работы алгоритма Краскала требуется n (n-1)/2 памяти ЭВМ для записи исходных данных, однако в процессе работы необходимо дополни-тельное время для проверки ребер на образование циклов.

Для работы алгоритма Прима памяти необходимо n², но зато отсутствует необходимость проверки ребер на образование циклов.

Следовательно, алгоритм Краскала требует в два с лишним раза меньше памяти, чем алгоритм Прима; зато машинного времени меньше необходимо при расчёте по алгоритму Прима. Кроме этого надо отметить, что алгоритм Краскала более прост при реализации.