Guruh talabalari: -guruh: – Dadajonov Hikmatillo

Prim algoritmi haqida batafsil
Algoritmni 1930 yilda chex matematikasi Voytox Yarnik, keyinroq mustaqil ravishda 1957 yilda kompyuter olimi Robert C. Prim tomonidan ishlab chiqilgan. 1959 yilda Edsger Dijkstra tomonidan qayta kashf qilingan. Algoritm uchta asosiy bosqichda ifodalanishi mumkin;
N tugunlari va har bir qirraning tegishli og'irligi bilan bog'langan grafikni hisobga olgan holda,
1. Grafikdan ixtiyoriy tugunni tanlang va uni T daraxtiga qo'shing (bu birinchi tugun bo'ladi)
2. Daraxtdagi tugunlarga ulangan har bir qirraning og'irligini ko'rib chiqing va minimalini tanlang. T daraxtining boshqa uchidagi chekka va tugunni qo'shing va qirrani grafikdan olib tashlang. (Ikki yoki undan ortiq minimallar mavjud bo'lsa, birini tanlang)
3. Daraxtga n-1 qirralari qo'shilmaguncha, 2-qadamni takrorlang.
Bu usulda daraxt bitta ixtiyoriy tugun bilan 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 (V ² ) vaqt murakkabligiga ega.
Kruskal algoritmi haqida
Jozef Kruskal tomonidan ishlab chiqilgan algoritm Amerika matematik jamiyati ishida 1956 yilda paydo bo'lgan. Kruskal algoritmini uchta oddiy qadam bilan ifodalash mumkin.
N tugunli grafik va har bir qirraning tegishli og'irligi hisobga olinsa,
1. Butun grafikning eng kichik og'irligi bo'lgan yoyni tanlang va daraxtga qo'shing va grafikdan o'chiring.
2. Qolganlardan, tsikl hosil qilmaydigan tarzda, eng kam vaznli chekkani tanlang. Daraxtga chekkasini qo'shing va grafikdan o'chiring. (Ikki yoki undan ortiq minimallar mavjud bo'lsa, birini tanlang)
3. Jarayonni 2 -bosqichda takrorlang.
Bu usulda algoritm eng kam qirrali bilan boshlanadi va har bir tsiklda har bir chekkani tanlashda davom etadi. Shuning uchun algoritmda grafikni ulash shart emas. Kruskal algoritmining vaqt murakkabligi O (logV)