Mavzu:Prima-deykstra algoritmi.Uni vaqt bo’yicha baholash.
Reja:
1.Kirish:
2.Primning minimal tejamkor daraxti (MST).
3.Deykstriyaning eng qisqa yo’l algoritmi.
4 Xulosa
5.Foydalanilgan adabiyotlar
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 .
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.
Dostları ilə paylaş: |
