Mustaqil ish ­­ cal015 (415) guruh talabasi Bajardi: Bahodirov Samandar Tekshirdi: Begimov O’ktam

https://kompy.info/algoritmlar.html?page=95
Kruskal algoritmi yo'naltirilmagan qirrali o'lchovli grafikaning minimal uzunlikdagi o'rmonini topadi . Agar grafik bog'langan bo'lsa , u minimal uzunlikdagi daraxtni topadi . (Bog'langan grafaning minimal uzunlikdagi daraxti - bu har bir tepalikni o'z ichiga olgan daraxtni hosil qiladigan qirralarning pastki qismi , bu erda daraxtdagi barcha qirralarning og'irliklari yig'indisi minimallashtiriladi. O'chirilgan grafik uchun minimal uzunlikdagi o'rmon har biri uchun eng kam chiqadigan daraxt iborat ulangan tarkibiy qismi .) Bu bo'lgan ochko'z algoritm bilan grafik nazariyasihar bir qadamda bo'lgani kabi, u minimal uzunlikdagi o'rmonga tsikl hosil qilmaydigan keyingi eng past vaznli chekkasini qo'shadi .


Ushbu algoritm birinchi bo'lib 1956 yilda Amerika Matematik Jamiyatining Ishlari, 48-50 betlarida paydo bo'lgan va Jozef Kruskal tomonidan yozilgan

Algoritm 

• 
  grafadagi har bir tepalik alohida daraxt bo'lgan F (daraxtlar to'plami) o'rmonini yarating
  
• 
  grafadagi barcha qirralarni o'z ichiga olgan S to'plamini yarating
  
• 
  esa S bo'lgan bo'sh bo'lmagan va F hali emas tarqalgan
  
  • 
    minimal og'irlikdagi chekkani S dan olib tashlang
    
  • 
    agar olib tashlangan chekka ikki xil daraxtni birlashtirsa, uni ikkita o'rmonni bitta daraxtga birlashtirib, F o'rmoniga qo'shib qo'ying
    

Algoritmni tugatgandan so'ng, o'rmon grafaning minimal uzunlikdagi o'rmonini hosil qiladi. Agar grafik bog'langan bo'lsa, o'rmon bitta komponentga ega va minimal daraxt daraxtini hosil qiladi.
Quyidagi kod ajratilgan ma'lumotlar tuzilishi bilan amalga oshiriladi . Bu erda biz o'z o'rmonimiz F ni qirralarning to'plami sifatida namoyish etamiz va ikkita vertikal bir daraxtning bir qismi ekanligini samarali aniqlash uchun ajratilgan ma'lumotlar tuzilmasidan foydalanamiz.