Kruskal vs Prim
Informatika fanida Prim va Kruskal algoritmlari ochkoʻz algoritm boʻlib, bogʻlangan vaznli yoʻn altirilmagan grafik uchun minimal oraliq daraxtini topadi. Yopuvchi daraxt - bu grafikning pastki grafigi bo'lib, grafikning har bir tuguni daraxt bo'lgan yo'l bilan bog'langan. Har bir yoyiladigan daraxtning vazni bor va barcha yoyiladigan daraxtlarning mumkin boʻlgan minimal ogʻirligi/narxi minimal kenglikdagi daraxt (MST).
Prim algoritmi haqida batafsil
Algoritm 1930-yilda chex matematigi Voytěch Yarnik tomonidan, keyinroq 1957-yilda kompyuter olimi Robert C. Prim tomonidan mustaqil ravishda ishlab chiqilgan. Uni 1959-yilda Edsger Deykstra qayta kashf etgan. Algoritm uchta asosiy bosqichda ifodalanishi mumkin;
N ta tugunli va har bir chekkaning tegishli ogʻirligi bilan bogʻlangan grafik berilgan boʻlsa, 1. Grafikdan ixtiyoriy tugunni tanlang va uni T daraxtiga qo'shing (bu birinchi tugun bo'ladi)
2. Daraxtdagi tugunlarga ulangan har bir chekkaning og'irliklarini ko'rib chiqing va minimalni tanlang. Daraxt T ning boshqa uchida chekka va tugunni qo'shing va qirrasini grafikdan olib tashlang. (Ikki yoki undan ortiq minimal qiymat mavjud boʻlsa, istalganini tanlang)
3. Daraxtga n-1 qirralari qo'shilmaguncha 2-bosqichni takrorlang.
Ushbu usulda daraxt bitta ixtiyoriy tugundan boshlanadi va har bir tsikl bilan shu tugundan boshlab kengayadi. Demak, algoritm to'g'ri ishlashi uchun grafik bog'langan grafik bo'lishi kerak. Prim algoritmining asosiy shakli O(V2) vaqt murakkabligiga ega.
Kruskal algoritmi haqida batafsil
Jozef Kruskal tomonidan ishlab chiqilgan algoritm 1956-yilda Amerika matematika jamiyati ishida paydo boʻlgan. Kruskal algoritmini uchta oddiy bosqichda ham ifodalash mumkin.
N ta tugunli grafik va har bir chetining tegishli ogʻirligi berilgan boʻlsa, 1. Butun grafikning eng kichik vazniga ega yoyni tanlang va daraxtga qo'shing va grafikdan o'chiring.
2. Qolganlardan eng kichik og'irlikdagi chekkani, tsiklni hosil qilmaydigan tarzda tanlang. Daraxtga chekka qo'shing va grafikdan o'chiring. (Ikki yoki undan ortiq minimal qiymat mavjud boʻlsa, istalganini tanlang)
3. 2-bosqichdagi jarayonni takrorlang.
Ushbu usulda algoritm eng kam ogʻirlikdagi chekkadan boshlanadi va har bir siklda har bir chetni tanlashda davom etadi. Shuning uchun, algoritmda grafikni ulash shart emas. Kruskal algoritmida vaqt murakkabligi O(logV)
Kruskal algoritmi va Prim algoritmi oʻrtasidagi farq nima?
• Prim algoritmi tugun bilan ishga tushadi, Kruskal algoritmi esa chekka bilan boshlanadi.
• Prim algoritmlari bir tugundan ikkinchisiga oʻtadi, Kruskal algoritmi esa chekka joylashuvi oxirgi bosqichga asoslanmaydigan tarzda qirralarni tanlaydi.
• Prim algoritmida grafik bogʻlangan grafik boʻlishi kerak, Kruskal esa uzilgan grafiklarda ham ishlashi mumkin.
• Prim algoritmining vaqt murakkabligi O(V2) va Kruskalning vaqt murakkabligi O(logV).
