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.
Do'stlaringiz bilan baham: |