Prim algoritmi qanday ishlaydi?

O`ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALAR VA KOMMUNIKATSIYALARNI RIVOJLANTIRISH VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALAR UNIVERSITETI QARSHI FILIALI

“Algoritmlarni loyihalash”

fanidan tayyorlagan
Mustaqil ishi
Mavzu: Prima-deykstra algoritmi.Uni vaqt bo’yicha baholash.

Topshirdi D.Egamberdiyev

Qabul qildi N.L.Xudoyorov
Mavzu: Prima-deykstra algoritmi.Uni vaqt bo’yicha baholash.
Reja:

1. 
   Primning minimal tejamkor daraxti (MST).
   
2. 
   Deykstriyaning eng qisqa yo’l algoritmi.
   
3. 
   Primning minimal tejamkor daraxti (MST) | Ochko'z Algo-5
   

Biz Kruskalning minimal tejamkorlik daraxti uchun algoritmini muhokama qildik . Kruskalning algoritmi singari, Prim algoritmi ham ochko'z algoritmdir . U bo'shashgan daraxtdan boshlanadi. G'oya ikkita vertikal to'plamni ushlab turishdir. Birinchi to'plamda allaqachon MST-ga kiritilgan uchlari mavjud, ikkinchisida esa hali mavjud bo'lmagan uchlari mavjud. Har qadamda, u ikkita to'plamni bog'laydigan barcha qirralarni ko'rib chiqadi va bu qirralarning minimal og'irligini tanlaydi. Yonni tanlaganingizdan so'ng, u chetning boshqa oxirgi uchini MST o'z ichiga olgan to'plamga o'tkazadi.
Grafikdagi ikkita uch uchini bog'laydigan qirralar guruhi grafik nazariyasida kesilgan deb nomlanadi . Shunday qilib, Prim algoritmining har bir bosqichida biz kesmani topamiz (ikkita to'plam, bittasida allaqachon MST kiritilgan va boshqa vertikal qismlar mavjud), kesmaning eng kam og'irligini tanlang va bu uchni MST Set-ga qo'shing. (allaqachon kiritilgan uchlarini o'z ichiga olgan to'plam).
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 .