Algoritmlarni layihalash




Download 247,14 Kb.
Pdf ko'rish
bet3/4
Sana24.05.2024
Hajmi247,14 Kb.
#252361
1   2   3   4
Bog'liq
5-mustaqil ishi

Kruskal algoritmi 
yo'naltirilmagan chekka og'irlikdagi grafikning minimal 
o'rmonini topadi . Grafik ulangan bo'lsa, u minimal kenglik daraxtini topadi. Bu
ochko'z algoritm bo'lib, har bir qadamda o'rmonga tsikl hosil qilmaydigan eng past 
og'irlikdagi chekka qo'shiladi. Algoritmning asosiy bosqichlari saralash va sikllarni 
aniqlash uchun ajratilgan maʼlumotlar strukturasidan foydalanish hisoblanadi. Uning
ishlash vaqti barcha grafik qirralarini og'irligi bo'yicha saralash vaqtiga bog'liq. 
Bog'langan og'irlikdagi grafikning minimal chegaraviy daraxti - bu pastki 
grafikdagi barcha qirralarning og'irliklarining yig'indisi minimal bo'lgan tsikllarsiz 
bog'langan subgraf. Ajratilgan grafik uchun minimal kenglikdagi o'rmon har bir 
ulangan komponent uchun minimal kenglikdagi daraxtdan iborat. 
Bu algoritm birinchi marta 1956 yilda Jozef Kruskal tomonidan nashr etilgan va 
tez orada Loberman & Weinberger (1957) tomonidan qayta kashf etilgan. Bu 
muammoning boshqa algoritmlariga Borůvka algoritmi , Jarník algoritmi va teskari 
oʻchirish algoritmi kiradi . 
Algoritm
[ tahrirlash ] 
Algoritm quyidagi amallarni bajaradi: 
Kirish grafikidagi har bir cho'qqi uchun dastlab alohida bitta cho'qqili daraxtdan 
iborat o'rmon (daraxtlar to'plami) yarating. 
Grafik qirralarini og'irlik bo'yicha tartiblang. 
Grafikning chetlari bo'ylab og'irliklari bo'yicha o'sish tartibida aylantiring. Har 
bir chekka uchun: 
Joriy oʻrmonga chekka qoʻshish sikl hosil qiladimi yoki yoʻqligini tekshiring 

Agar yo'q bo'lsa, ikkita daraxtni bitta daraxtga birlashtirib, o'rmonga chekka 
qo'shing 
Algoritm tugagandan so'ng, o'rmon grafikning minimal o'rmonini hosil 
qiladi. Agar grafik bog'langan bo'lsa, o'rmon bitta komponentga ega va minimal 
kenglikdagi daraxtni hosil qiladi. 

Download 247,14 Kb.
1   2   3   4




Download 247,14 Kb.
Pdf ko'rish