Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalar universiteti mustaqil ish



Yüklə 19,08 Kb.
tarix02.05.2023
ölçüsü19,08 Kb.
#106136
Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalar un




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

Yüklə 19,08 Kb.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin