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
|
