Kompyuter injineringi ” fakulteti 2 – bosqich cal009 guruh talabasining

Kruskal algoritmi.

Ushbu algoritm 1956 yili Kruskal tomonidan ishlab chiqilgan.

Faraz qilamiz, V = {1, 2, .... n} tugunlar to‘plamidan iborat va E qirralar to‘plamida aniqlangan s narx funksiyasi bilan berilgan G=(V, E) bog‘langan graf bo‘lsin. Kruskal algoritmida G graf uchun minimal narxli daraxtlar skeletini qurish G grafning faqat n ta tugunlaridan tashkil topgan va qirralari bo‘lmagan T=(V, ø) grafdan boshlanadi. Shunday qilib, har bir tugun bog‘langan (o‘zi-o‘zi bilan) komponent hisoblanadi. Algoritm bajarilishi vaqtida bog‘langan komponentlar naboriga ega bo‘lamiz, asta-sekin birlashtirib daraxtlar skeletini tashkillashtiramiz.
Asta-sekin o‘suvchi bog‘langan komponentlarni qurishda E to‘plamdan qirralar ularning narxi o‘sishi tartibida navbatma-navbat tekshiriladi. Agar navbatdagi qirra turli komponentlardagi ikkita tugunni birlashtirsa, u holda bu qirra T grafga qo‘shiladi. Agar bu qirra bitta komponentning ikkita tugunini birlashtirsa, u tashlab yuboriladi, chunki uning bog‘langan komponentga qo‘shilishi sikl hosil bo‘lishiga olib keladi. G grafning barcha tugunlari bitta komponentga tegishli bo‘lsa, T minimal narxli daraxtlar skeletini qurish bu graf uchun tugaydi.

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

Quyida 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: