Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalar universiteti mustaqil ish

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALAR UNIVERSITETI MUSTAQIL ISH Mavzu: Graflarni eng arzon tayanch daraxtini qurishda Kruskal xasis algoritmi Variant 5 Bajardi: Gofurov Nodirjon Reja : 1.krushal algaritmi 2.c++ da tahlili 3.pythonda tahlili 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. algorithm Kruskal(G) is F:= ∅ for each v ∈ G.V do MAKE-SET(v) for each (u, v) in G.E ordered by weight(u, v), increasing do if FIND-SET(u) ≠ FIND-SET(v) then F:= F ∪ {(u, v)} ∪ {(v, u)} UNION(FIND-SET(u), FIND-SET(v)) return F