Mavzu: Graflarni eniga va bo‘yiga aylanishi reja: Ketma-ketliklar, to‘plamlar, daraxtlar, graflarni ifodalash usullari Graflarni eniga va bo‘yiga aylanishi Graflarning eng arzon tayanch daraxtini qurishda Kruskal xasis algoritmi

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.

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.