Referat tekshirdi: Vaffoyev Sunnatillo Mustaqil ish

“Kompyuter injiniringi” fakulteti

Guruh nomi: 710-22.

Tekshirdi: Vaffoyev Sunnatillo

Variant-12

Reja:

1. 
   Kruskal algoritmiga kirish.
   

2. 
   Daraxtlarni o'z ichiga olgan va minimal bo'lgan daraxtlar.
   

3. 
   Kruskal algoritmining ochko'z yondashuvi.
   

4. 
   Kruskal algoritmini bosqichma-bosqich bajarish.
   

5. 
   Boshqa Minimal Spanning Daraxt Algoritmlari bilan solishtirish.
   

Kruskal algoritmi quyidagi tartibda ishlaydi:

1. 
   Barcha graf qo'shimchalari qimmati bo'yicha saralangan.
   
2. 
   Algoritm boshlang'ich darajada bo'lgan bo'ylgan ro'yxatni qo'shimchalarga ochadi.
   
3. 
   Har bir qo'shimchani qo'shish uchun, uni qanday tug'unlar bilan ulashishini tekshiradi.
   
4. 
   Agar qo'shimcha o'zini grafdagi uzluksizlik tizimi yaratmasa, uni qo'shib olamiz va grafimizni daraxtning tizimi bilan boshqarish uchun ishlatiladigan bo'ylgan qo'shimchalar ro'yxatiga qo'shamiz.
   
5. 
   Bu jarayon hamma qo'shimchalarni biriktirish va grafdagi barcha tug'unlarni bog'laydigan eng kichik tizimni olish bilan takrorlanadi.
   
6. 
   Algoritmdi barcha qo'shimchalarni qo'shishdan so'ng, grafimiz daraxt tizimi bo'lgan va minimum tashqi qo'shimchalarning miqdori eng kam bo'lgan daraxtni quriladi.
   

Kruskal algoritmi og'irlikdagi, yo'naltirilmagan grafikning minimal oraliq daraxtini (MST) topish uchun asosiy va keng qo'llaniladigan texnikadir. 1956 yilda kompyuter olimi Jozef Kruskal tomonidan ishlab chiqilgan ushbu ochko'z algoritm ushbu klassik grafik nazariyasi muammosini hal qilishda soddaligi va samaradorligi bilan mashhur. MST - bu asl grafikning pastki grafigi bo'lib, u barcha cho'qqilarni minimal umumiy chekka og'irligi bilan bog'laydi, shu bilan birga tsikllar yo'qligini ta'minlaydi.