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

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 ² ) 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)