23-laboratoriya mashguloti Mavzu: Kruskal algoritmi. Prima algoritmi. Xoffman algoritmi. Nazariy qism Kruskal va boshqalar



Download 24,95 Kb.
bet1/2
Sana06.07.2022
Hajmi24,95 Kb.
#749624
  1   2
Bog'liq
23-laboratoriya mashguloti Mavzu Kruskal algoritmi. Prima algor


23-laboratoriya mashguloti
Mavzu: Kruskal algoritmi. Prima algoritmi. Xoffman algoritmi.
Nazariy qism
Kruskal va boshqalar
 Informatika fanida Prim va Kruskal algoritmlari ochko'z algoritm bo'lib, u bog'langan og'irlikdagi yo'naltirilmagan grafik uchun minimal daraxtni topadi. Qatlamli daraxt - bu grafikning pastki grafigi, shuning uchun grafikning har bir tuguni yo'l bilan bog'lanadi, bu daraxt. Har bir daraxtning og'irligi bor, va barcha daraxtlar uchun mumkin bo'lgan minimal og'irlik/xarajat - bu eng kam daraxt (MST).
Prim algoritmi haqida batafsil
Algoritmni 1930 yilda chex matematikasi Voytox Yarnik, keyinroq mustaqil ravishda 1957 yilda kompyuter olimi Robert C. Prim tomonidan ishlab chiqilgan. 1959 yilda Edsger Dijkstra tomonidan qayta kashf qilingan. Algoritm uchta asosiy bosqichda ifodalanishi mumkin;
N tugunlari va har bir qirraning tegishli og'irligi bilan bog'langan grafikni hisobga olgan holda,
1. Grafikdan ixtiyoriy tugunni tanlang va uni T daraxtiga qo'shing (bu birinchi tugun bo'ladi)
2. Daraxtdagi tugunlarga ulangan har bir qirraning og'irligini ko'rib chiqing va minimalini tanlang. T daraxtining boshqa uchidagi chekka va tugunni qo'shing va qirrani grafikdan olib tashlang. (Ikki yoki undan ortiq minimallar mavjud bo'lsa, birini tanlang)
3. Daraxtga n-1 qirralari qo'shilmaguncha, 2-qadamni takrorlang.
Bu usulda daraxt bitta ixtiyoriy tugun bilan boshlanadi va har bir tsikl bilan shu tugundan boshlab kengayadi. Demak, algoritm to'g'ri ishlashi uchun grafik bog'langan grafik bo'lishi kerak. Prim algoritmining asosiy shakli O (V 2 ) vaqt murakkabligiga ega.
Kruskal algoritmi haqida
Jozef Kruskal tomonidan ishlab chiqilgan algoritm Amerika matematik jamiyati ishida 1956 yilda paydo bo'lgan. Kruskal algoritmini uchta oddiy qadam bilan ifodalash mumkin.
N tugunli grafik va har bir qirraning tegishli og'irligi hisobga olinsa,
1. Butun grafikning eng kichik og'irligi bo'lgan yoyni tanlang va daraxtga qo'shing va grafikdan o'chiring.
2. Qolganlardan, tsikl hosil qilmaydigan tarzda, eng kam vaznli chekkani tanlang. Daraxtga chekkasini qo'shing va grafikdan o'chiring. (Ikki yoki undan ortiq minimallar mavjud bo'lsa, birini tanlang)
3. Jarayonni 2 -bosqichda takrorlang.
Bu usulda algoritm eng kam qirrali bilan boshlanadi va har bir tsiklda har bir chekkani tanlashda davom etadi. Shuning uchun algoritmda grafikni ulash shart emas. Kruskal algoritmining vaqt murakkabligi O (logV)

Download 24,95 Kb.

Do'stlaringiz bilan baham:
  1   2




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish