Tekshirdi: Begimov O’ktam Toshkent 2023 Mavzu: Prima Deykstra algoritmi. Uni vaqt bo'yicha baholasho. Reja

Prim algoritmi
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.
3) mstSet-da barcha vertikal qismlar mavjud emas

1. 
   tepalik nuqtasiga Pick U erda emas mstSet va minimal muhim ahamiyatga ega. 
   
2. 
    mstSet-ga u qo'shing.
   
3. 
    u- ning barcha qo'shni uchlarining kalit qiymatini yangilang. Kalit qiymatlarini yangilash uchun barcha qo'shni vertikalar bo'ylab takrorlang. Har qo'shni uch uchun v chet vazn bo'lsa, UV kam avvalgi asosiy qiymati qaraganda V, og'irligi sifatida kalit qiymati yangilash UV
   

Kalit qiymatlarni ishlatish g'oyasi kesilgan joydan minimal og'irlik chegarasini tanlashdir. Kalit qiymatlari faqat MST-ga kiritilmagan uchlari uchun ishlatiladi, bu uchlari uchun kalit qiymati ularni MST ichiga kiritilgan uchlari bilan bog'laydigan minimal og'irliklarni bildiradi.

Quyidagi misol bilan tushunaylik.

O'rnatilgan mstSet dastlab bo'sh va vertikallarga berilgan kalitlar {0, INF, INF, INF, INF, INF, INF, INF}, bu erda INF cheksizdir. Endi minimal kalit qiymatiga ega vertexni tanlang. Vertex 0 tanlangan, uni mstSet-ga qo'shing . Shunday qilib, mstSet {0} bo'ladi. MstSet- ga qo'shgandan so'ng , qo'shni vertikallarning kalitlarini yangilang. 0 ga ulashgan vertikallar 1 va 7 dir. 1 va 7 ning asosiy qiymatlari 4 va 8 kabi yangilanadi. Quyidagi subgrafda vertikal chiziqlar va ularning asosiy qiymatlari ko'rsatilgan, faqat cheklangan kalit qiymatlari bo'lgan uchlari ko'rsatilgan. MST-ga kiritilgan uchlari yashil rangda ko'rsatilgan.

Minimal kalit qiymatiga ega va MST-ga kirmagan (mstSET-da emas) vertikalni tanlang. 1 vertex tanlangan va mstSet-ga qo'shilgan. Endi mstSet {0, 1} bo'ladi. Qo'shni uchlarining kalit qiymatlarini yangilang. 1-sonning 8 qiymati 8 ga teng.

Minimal kalit qiymatiga ega va MST-ga kirmagan (mstSET-da emas) vertikalni tanlang. Biz 7 ta vertexni yoki 2 ta vertexni tanlashimiz mumkin, vertex 7 ni tanlaymiz. Endi mstSet {0, 1, 7} bo'ladi. 7-sonli ulashgan vertikallarning kalit qiymatlarini yangilang. 6 va 8-vertekslarning kalit qiymati cheklangan bo'ladi (mos ravishda 1 va 7).

Minimal kalit qiymatiga ega va MST-ga kirmagan (mstSET-da emas) vertikalni tanlang. Vertex 6 tanlangan. Endi mstSet {0, 1, 7, 6} bo'ladi. 6-sonli ulashgan tepaliklarning kalit qiymatlarini yangilang. 5 va 8-vertexlarning kalit qiymati yangilanadi.

MstSet berilgan grafikning barcha uchlarini o'z ichiga olguncha yuqoridagi amallarni takrorlaymiz . Va nihoyat, biz quyidagi grafikni olamiz.

SPT tarkibiga kiruvchi uchlari to'plamini ifodalash uchun sptSet [] boolean massividan foydalanamiz. Agar sptSet [v] qiymati to'g'ri bo'lsa, v vertex SPTga kiritilgan, aks holda emas. Array dist barcha vertikallarning eng qisqa masofa qiymatlarini saqlash uchun ishlatiladi.