O’zbekiston respublikasi raqamli texnologiyalar vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti mustaqil ish Graflarni eniga va bo’yiga aylanish (tekshirish) Bajardi: Nuriddinov Diyorbek Guruh

Masalani yechish algoritmi (Kruskal usuli): Kruskal algoritmining bajaralishi quyidagicha amalaga oshiriladi.

Kruskal algoritmidan foydalangan holda MSTni topish bo'yicha qadamlar keltirilgan:

1. 
   Barcha qirralarni vaznining o’sish tartibida saralash.
   
2. 
   Eng kichik tugunni tanlang. Hozirgacha shakllangan daraxt bilan sikl hosil qiladimi yoki yo'qligini tekshirib ko'ring. Agar sikl shakllanmagan bo'lsa, ushbu tugunni kiriting. Boshqalari, tashlab yuboring.
   
3. 
   Yopilgan daraxtda (V-1) qirralar bo'lguncha # 2-bosqichni takrorlang.
   

STL yordamida Kruskal algoritmini amalga oshirishda biz uchun foydali bo'lgan ba'zi bir muhim fikrlar.

1. 
   Grafadagi barcha qirralardan iborat qirralarning vektoridan foydalaning va vektorning har bir elementi uchta parametrni o'z ichiga oladi: manba, manzil va manba va manzil orasidagi tugun narxi.
   

vector
> > edges;

2. 
   Bu erda tashqi juftlikda (ya'ni juftlik >) birinchi element tugun narxiga to'g'ri keladi, ikkinchi element o'zi juft bo'lib, u tugunning ikkita tepasini o'z ichiga oladi.
   
3. 
   Qirralarni o’sish tartibda saralash uchun ichki std :: sort dan foydalaning; 
   
4. 
   Birlashma topish algoritmidan foydalanamiz, agar u joriy tugun MSTga qo'shilsa, sikl hosil qiladimi. Agar ha rad etsa, uni qo'shib qo'ying (birlashma).
   

Ushbu algoritm O (M log N + N2) vaqtda bajariladi. Qirralarni saralash uchun O (M logN) ta operasiya kerak bo’ladi. Tugun u yoki bu qism daraxtga tegishli bo‘lsa, tree_id massiv yordamida saqlanadi, bu massivda har bir tugun uchun u tegishli bo‘lgan daraxt nomeri saqlanadi. Har bir qirra uchun O (1) vaqtda uning tugunlari turli daraxtlarga tegishli ekanligini aniqlanadi. Nihoyat, ikkita daraxtni birlashtirish O (N) vaqtda bajariladi. Birlashtirish operatori O(N) o‘tishda bajarilishini hisobga olsak, O (M log N + N2) kelib chiqadi.

Dastur kodi: