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

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

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).