Amaliy ish №13 Mavzu: Kruskal algoritmi. Prima algoritmi. Xoffman daraxtlari Minimal kenglikdagi daraxt. Kruskal algoritmi

2. Prima algoritmi
Minimal kenglikdagi daraxt. Prim algoritmi
n ta uchi va m qirrasi boʻlgan ogʻirlikdagi yoʻnaltirilmagan G graf berilgan. Ushbu grafikning barcha uchlarini bog'laydigan va shu bilan birga eng kichik vaznga (ya'ni qirra og'irliklarining yig'indisi) ega bo'lgan pastki daraxtini topish talab qilinadi. Pastki daraxt - bu barcha cho'qqilarni bog'laydigan qirralarning to'plami va istalgan uchdan boshqasiga aniq bitta oddiy yo'l bilan kirishingiz mumkin.

Bunday pastki daraxt minimal kenglikdagi daraxt yoki oddiygina minimal kenglikdagi daraxt deb ataladi. Har qanday grafda n-1 qirralari bo'lishini tushunish oson.

Tabiiy sharoitda bu muammo quyidagicha ko'rinadi: n ta shahar bor va har bir juftlik uchun ularni yo'l bilan ulash narxi ma'lum (yoki ularni bog'lab bo'lmasligi ma'lum). Barcha shaharlarni shunday bog'lash talab etiladiki, istalgan shahardan boshqasiga borish mumkin bo'ladi va shu bilan birga yo'l yotqizish xarajatlari minimal bo'ladi.
Prim algoritmi
Bu algoritm 1957 yilda ushbu algoritmni kashf etgan amerikalik matematik Robert Prim sharafiga nomlangan. Biroq, 1930 yilda bu algoritmni chex matematigi Voytex Yarnik kashf etgan. Bundan tashqari, Edsger Dijkstra ham 1959 yilda ulardan mustaqil ravishda ushbu algoritmni ixtiro qilgan.
Algoritmning tavsifi
Algoritmning o'zi juda oddiy. Kerakli minimal skelet, bir vaqtning o'zida qirralarni qo'shib, asta-sekin quriladi. Dastlab, skelet bitta vertexdan iborat deb taxmin qilinadi (u ixtiyoriy tanlanishi mumkin). Keyin, ushbu uchdan chiqadigan minimal og'irlik qirrasi tanlanadi va minimal oraliq daraxtga qo'shiladi. Shundan so'ng, skelet allaqachon ikkita cho'qqini o'z ichiga oladi va endi minimal og'irlikning chekkasi qidiriladi va qo'shiladi, bir uchi tanlangan ikkita cho'qqidan birida, ikkinchisi esa aksincha, bu ikkitadan tashqari qolganlarida. Va hokazo, ya'ni. har safar minimal og'irlik qirrasi qidiriladi, uning bir uchi allaqachon skeletga olingan uchdir, ikkinchi uchi esa hali olinmagan va bu chekka skeletga qo'shiladi (agar bir nechta bunday qirralar bo'lsa, siz istalganini oling). Ushbu jarayon kengaytma daraxti barcha uchlarini (yoki ekvivalenti, n-1 qirralarini) o'z ichiga olguncha takrorlanadi.

Natijada, minimal bo'lgan skelet quriladi. Agar grafik dastlab ulanmagan bo'lsa, u holda hech qanday kengaytmali daraxt topilmaydi (tanlangan qirralarning soni n-1 dan kam bo'lib qoladi).

Amalga oshirish
Algoritmning ishlash vaqti, asosan, mos qirralar orasidan keyingi minimal qirrani qanday izlashimizga bog'liq. Turli xil asimptotiklarga va turli xil ilovalarga olib keladigan turli yondashuvlar bo'lishi mumkin.
amalga oshirish: O(nm) va O(n² + m log n) algoritmlari
Agar har safar biz barcha mumkin bo'lgan variantlarni ko’rish orqali qirra izlasak, unda barcha mumkin bo'lganlar orasida eng kichik og'irlikdagi qirrani topish uchun asimptotik ravishda O(m) qirralarni ko’rish kerak bo'ladi. Bu holda algoritmning umumiy asimptotikasi O(nm) bo'ladi, bu eng yomon holatda O(n^3) bo'ladi, bu juda sekin algoritmdir.

Bu algoritmni yaxshilash mumkin, agar har safar barcha qirralar emas, balki tanlangan har bir uchdan faqat bitta qirra tekshirilsa. Buni amalga oshirish uchun, masalan, har bir uchdan qirralarni og'irliklarning o'sish tartibida saralashingiz va ko'rsatgichni birinchi ruxsat etilgan chetiga saqlashingiz mumkin (esda tuting, faqat hali tanlanmagan uchlar to'plamiga olib keladigan qirralarga ruxsat beriladi). Keyin, agar skeletga har safar qirra qo'shilganda bu ko'rsatkichlarni qayta hisoblab chiqsak, algoritmning umumiy asimptotikasi O(n² + m) bo'ladi, lekin avval O(m ) dagi barcha qirralarni tartiblash kerak bo'ladi. log n), bu eng yomon holatda (zich graf uchun) O(n² log n) asimptotikani beradi.