19. Прима-Дeйкстра алгoритми. Вақт бўйича самарадoрлигини баҳoлаш

Prim algoritmi qanday ishlaydi? Prim algoritmining g'oyasi oddiy, kengaytirilgan daraxt barcha uchlari bir-biriga ulangan bo'lishi kerak. Shunday qilib, uchburchak  daraxtiqilish uchun vertikal qismlarning ikkita ajratilgan pastki qismlari (yuqorida muhokama qilingan) ulanishi kerak . Va uni minimal  cho'zish daraxtiqilish uchun ular minimal vazn chegarasi bilan bog'langan bo'lishi kerak .

Algoritm
1) MST-ga kiritilgan vertikallarni hisobga oladigan mstSet to'plamini yarating.
2) Kirish grafigidagi barcha uchlarga kalit qiymatini belgilang. INFINITE sifatida barcha muhim qadriyatlarni boshlang. Kalit qiymatini birinchi vertex uchun 0 deb belgilang, shunda u birinchi tanlanadi.