logo
  1. Главная страница
  2. Дипломные работы
  3. Общий
  4. KRASKAL ALGORITMI

KRASKAL ALGORITMI

Загружено в:

12.08.2023

Скачано:

0

Размер:

439.9208984375 KB
Скачать
“KRASKAL ALGORITMI” MAVZUSIDA TAYYORLAGAN Mundarija Kirish. ............................................................................................................................................................................. 2 Kraskal algoritmi. ............................................................................................................................................................ 3 Kraskal algoritmining tavsifi. ......................................................................................................................................... 7 Algoritmning psevdokodi. ............................................................................................................................................ 16 Kraskalning minimal kengayuvchi daraxt algoritmi. .................................................................................................... 20 Algoritmning amaliy qismi. .......................................................................................................................................... 28 Kraskal algoritmining murakkabligi. ............................................................................................................................ 35 Xulosa. .......................................................................................................................................................................... 40 Foydanilgan adabiyotlar. ............................................................................................................................................... 41 1 Kirish. Kurs ishining o’rganish ob’ekti Kraskal algoritmini amalga oshirish edi. Ishning maqsadlari quyidagilar edi: 1)kraskal algoritmi, uning tarixi bilan tanishish; 2)minimal kenglikdagi daraxtni qurish algoritmini amalga oshirish; 3)algoritmning murakkabligini tahlil qilish; 4)algoritmni sinash. Bog’langan vaznli grafning minimal oraliq daraxti (MOD) uning bog’langan pastki grafigi bo’lib, u asl daraxtning barcha uchlari va uning ba’zi qirralaridan iborat bo’lib, qirralarning og’irliklarining yig’indisi maksimal mumkin. Agar asl graf uzilgan bo’lsa, unda quyida tavsiflangan protsedura uning har bir ulangan komponentiga navbat bilan qo’llanilishi mumkin va shu bilan ushbu komponentlar uchun minimal oraliq daraxtlarni olish mumkin. Kraskal algoritmi (yoki Kraskal algoritmi) vaznli bog langan yo naltirilmagan graf uchun minimal oraliqli daraxtniʻ ʻ qurish algoritmidir. Algoritm birinchi marta 1956 yilda Jozef Kraskal tomonidan tasvirlangan. Kraskal algoritmi bir vaqtning o’zida bir nechta bog’langan komponentlar uchun daraxt qurishi mumkin, ular hal qilish jarayonida bitta bog’langan daraxtga birlashtiriladi. To’liq graf qirralarning ro’yxati bilan berilgan. Yugurishdan oldin qirralarning ro’yxati uzunlik bo’yicha o’sish tartibida tartiblanadi. Har bir bosqichda qirralarning ro’yxati ko’rib chiqiladi, oldingi bosqichdagi yechimga kiritilganidan keyingi qirraidan boshlab, eritma ichiga kiritilgan qirralar bilan sikl hosil qilmaydigan qirra pastki daraxtga qo’shiladi. qurilish ishlari olib borilmoqda. Daraxtning minimal uzunligini topish muammosi ko’pincha shunga o’xshash sharoitda yuzaga keladi: n ta shahar bor, ular orqali siz istalgan shahardan boshqasiga (to’g’ridan-to’g’ri yoki boshqa shaharlar orqali) borishingiz mumkin bo’lgan marshrutni yotqizishingiz mumkin. Yo’l haqi maksimal bo’lishi uchun shunday marshrutni topish talab qilinadi. Amalda Kraskal 2 algoritmi aviakompaniyalar tomonidan bir yo’nalishdan ikkinchisiga eng qisqa havo yo’lini topishda qo’llaniladi. Kraskal algoritmi. Kraskal algoritmi bog’langan vaznli graf uchun minimal oraliq daraxtini topish uchun ishlatiladi. Algoritmning asosiy maqsadi biz grafning har bir tugunini kesib o’tishimiz mumkin bo’lgan qirralarning pastki to’plamini topishdir. U global optimalga e’tibor qaratish o’rniga har bir bosqichda optimal echim topadigan greedy yondashuvga amal qiladi. Kraskal algoritmi bu grafning MODni topish uchun boshqa mantiqdan foydalanadigan yana bir mashhur minimal oraliqli daraxt algoritmi. Kraskal algoritmi tugundan boshlash o’rniga, barcha qirralarni past og’irlikdan yuqoriga saralaydi va siklni yaratadigan qirralarga e’tibor bermasdan, eng past qirralarni qo’shishda davom etadi. Kraskal algoritmi dastlab har bir tugunni o’z daraxtiga joylashtiradi, so’ngra bu daraxtlarni asta-sekin birlashtirib, har bir iteratsiyada qaysidir qirrada ikkita ma’lum daraxtni birlashtiradi. Algoritmni boshlashdan oldin barcha qirralarning vazni bo’yicha (kamaymaslik tartibida) tartiblanadi. Keyin birlashtirish jarayoni boshlanadi: barcha qirralar birinchisidan oxirgisiga (tartib tartibida) o’tkaziladi va agar joriy qirraning uchlari turli pastki daraxtlarga tegishli bo’lsa, u holda bu pastki daraxtlar birlashtiriladi va javobga qirra qo’shiladi. Barcha qirralarni sanab o’tish oxirida barcha tugunliklar bir xil pastki daraxtga tegishli bo’ladi va javob topiladi. Bizda quyidagi yo’naltirilmagan vaznli graf mavjud, grafning barcha tugunlarini o’z ichiga olgan pastki graf, ya’ni daraxt bo’lgan kengaytmali daraxt deb ataymiz va vazifa - qirralarining yig’indisi minimal bo’lgan bunday kengaygan daraxtni topishdir. Asl grafni qirralarsiz tasavvur qiling, endi siz barcha tugunlarni qandaydir tarzda bir-biriga bog’lashingiz kerak, shunda siz istalgan tugundan ikkinchisiga 3 o’tishingiz mumkin, natijada olingan grafda kiritilgan qirralarning og’irliklarining minimal mumkin bo’lgan yig’indisi bilan sikllarsiz ishlaydi. Ushbu algoritmning ishlash mexanizmi juda oddiy. Kirish qismida bo’sh subgraf mavjud bo’lib, biz uni potentsial minimal kenglikdagi daraxtga yakunlaymiz. Biz faqat bog’langan graflarni ko’rib chiqamiz, aks holda Kraskal algoritmini qo’llashda biz minimal kenglikdagi daraxtni emas, balki oddiygina o’rmonni olamiz.  Birinchidan, biz qirralarni og’irliklari bo’yicha kamaymaydigan tartibda saralaymiz.  Biz subgrafimizga qirra qo’shamiz i- ое , agar bu qirra ikki xil bog’langan komponentni bog’lasa, ulardan biri bizning subgrafimizdir. Ya’ni, har bir qadamda minimal og’irlik qirrasi qo’shiladi, uning bir uchi bizning subgrafimizda mavjud, ikkinchisi esa hali yo’q.  Algoritm o’z ishini subgrafimizning tugunlari to’plami asl grafning tugunlari to’plamiga to’g’ri kelgandan keyin yakunlaydi. Ushbu algoritm greedy deb ataladi, chunki har bir qadamda biz umuman optimal yechimga olib keladigan eng yaxshi variantni topishga harakat qilamiz. Muayyan misolni bosqichma-bosqich tahlil qilish. Quyda keltirilgan grafdan biz uning barcha qirralarini tartiblangan tartibda yozamiz, va biz ushbu qirralarni ro’yxatdagi skeletimizga qo’shishni boshlaymiz: 1) D <--> B; w = 2 2) D <--> C; w = 6 4 3) A <--> B; w = 7 4) A <--> C; w = 8 5) C <--> E; w = 9 6) D <--> F; w = 9 7) F <--> E; w = 10 8) B <--> C; w = 11 9) D <--> E; w = 11 1-qirra qo’shgandan keyin pastki chiziq 2 va 3 qirralarni qo’shgandan so’ng subgraph A <--> C Ko’rib turganingizdek, bizning kengaygan daraxtimizga qirra qo’shsangiz, sikl hosil bo’ladi, shuning uchun biz bu qirrani o’tkazib yuboramiz. Natijada, bizda quyidagi subgraf bor va siz sezganingizdek, biz barcha tugunlarni qirralar bilan minimal mumkin bo’lgan og’irliklar bilan birlashtirdik, ya’ni biz asl grafmiz uchun minimal oraliq daraxtini topdik. 5 MOD ni graphonline -da topish uchun biz o’rnatilgan algoritm bilan tekshiramiz va biz pastki graflar bir xil ekanligini ko’ramiz agar qirralarning og’irligi teng bo’lsa, biz ulardan istalganini tanlashimiz mumkinligi sababli, eng kam kenglikdagi daraxtlar bo’lgan oxirgi subgraflar ba’zi qirralarga qadar farq qilishi mumkin. Istalgan MODning umumiy og’irligi 33 ni tashkil qiladi. Amalga oshirish . Taqdim etilgan algoritmni amalga oshirishning eng oson yo’li – KST (kesishmayotgan segmentlar tizimi) yordamida. Avval aytib o’tganimizdek, qirralarning og’irligiga qarab kamaymaydigan tartibda saralash kerak. Bundan tashqari, funktsiya chaqiruvlari yordamida biz har bir tugunni o’z daraxtimizga joylashtirishimiz mumkin, ya’ni biz ma’lum bir pastki graf to’plamini yaratamiz. Keyin biz barcha qirralarni tartiblangan tartibda takrorlaymiz va joriy qirraning tushayotgan uchlari funktsiyadan foydalangan holda turli pastki graflarga tegishli yoki yo’qligini ko’ramiz, agar ikkala uchi ham turli komponentlarda bo’lsa, u holda funksiya yordamida ikkita turli pastki grafni birlashtiramiz. 6 Kraskal algoritmining tavsifi. Algoritm V turli guruhlardan boshlanadi (bu erda V - grafdagi tugunlar soni). Jarayonning har bir bosqichida grafning minimal og’irligi bo’lgan qirra tanlanadi va minimal oraliq daraxtga qo’shiladi. Qirra faqat shunday tarzda tanlanadi, agar u sikl yaratmasa - agar minimal og’irlikdagi qirra minimal oraliq daraxtda siklni keltirib chiqarsa, algoritm ikkinchi minimal og’irlikdagi qirra bilan davom etadi. Grafga qirra qo’shish, shuningdek, ikkala tugunni ham bir guruhga aylantiradi (esda tutingki, har bir tugun dastlab alohida guruhlarda boshlanadi). Algoritm tugagandan so’ng, faqat bitta guruh qoladi, bu esa minimal kenglikdagi daraxtni ifodalaydi. C++ Kraskal algoritmi Prim algoritmidan bir oz boshqacha ishlaydi. Prim algoritmi tugunlarni ushbu guruhga suradi va uni minimal og’irlikdagi qirrani tashkil etuvchi ikkita tugundan boshlab birma-bir kengaytiradi. Kraskal algoritmi tugunlarga emas, balki qirralarga ko’proq taalluqlidir va ularning uchlarini umumiy guruhga qo’shish orqali to’g’ridan-to’g’ri qirralar bilan shug’ullanadi. C++ da Kraskal algoritmini amalga oshirishning ikkita asosiy usuli mavjud: ajratilgan to’plamlar yoki ustuvor navbatlar. Ajratilgan to’plamlardan foydalanish biroz yaxshiroq, chunki u istalgan vaqtda guruhlardagi o’zgarishlarni tasavvur qilishga yordam beradi. Algoritm quyidagicha: - 1. Tugunlar guruhlarini saqlash uchun massivni ishga tushiring. 2. Graf qirralarini ularning og’irliklari bilan saqlash uchun massivni ishga tushiring. 3. Yopuvchi daraxtni bo’sh massiv sifatida ishga tushiring. 7 4. Grafning barcha uchlarini turli guruhlarga qo’ying. 5. Qirralar qatorini og’irliklarning ortib borishi bo’yicha tartiblang. 6. Kenarlarning tartiblangan qatorida boshqa qirra qolmaguncha 7-bosqichni davom ettiring 7. Agar qirraning bir tugunining guruhi qirraning boshqa tugunining guruhiga to’g’ri kelmasa, ularni ikkalasini ham bir guruhga qo’shing va qirrani kengaytirilgan daraxt qatoriga qo’shing. 8. Spaning-tree massivi bo’ylab takrorlang va qirralarning og’irliklarini qo’shing. 9. Olingan qirralarning yig’indisi eng kam yoyiladigan daraxtning og’irligini tashkil qiladi, shu bilan birga kengayuvchi daraxtlar qatori ham xuddi shunday qirralarni o’z ichiga oladi. Keling, bir misol ishlab chiqaylik. Yuqoridagi grafni ko’rib chiqing va unga Kraskal algoritmini qo’llashga harakat qilaylik. 8 Dastlab, biz minimal vaznga ega bo’lgan birinchi qirrani tanlashimiz kerak. Bu erda AB tanlanadi, uning og’irligi 10 ga teng. 9 Endi biz ikkinchi minimal og’irlik bilan qirrasini tanlaymiz. Bu erda disk og’irligi 13 bo’lgani uchun tanlanadi. 10 Keyinchalik davom etsak, minimal og’irlikdagi qirra BC ekanligini aniqlaymiz. Ushbu qirraning og’irligi 18 ga teng. 11 To’liq daraxt olinganligi sababli, biz algoritmni bu erda to’xtatamiz. Shu tarzda olingan daraxtning minimal og’irligi 10+18+13=41. Dastlab, joriy qirralar to’plami bo’sh qilib o’rnatiladi. Keyin, iloji bo’lsa, quyidagi operatsiya amalga oshiriladi: mavjud to’plamga qo’shilishi unda sikl paydo bo’lishiga olib kelmaydigan barcha qirralardan minimal og’irlikning qirrasi tanlanadi va allaqachon mavjud to’plamga qo’shiladi. Bunday qirralar qolmaganda, algoritm tugallanadi. Berilgan grafning barcha tugunlari va topilgan qirralari to’plamini o’z ichiga olgan pastki grafigi uning minimal og’irlikdagi daraxtidir. Algoritm quyidagi harakatlar ketma-ketligidan iborat: E qirralari ro yxati tuziladi, unda qirraning uzunligi, qirraning boshlang ich cho qqisi soni (i),ʻ ʻ ʻ 12 qirraning oxirgi uchi soni (j) va bu qirraga kiritilganligi belgisi ko rsatilgan daraxt.ʻ 2. Ushbu ro’yxat qirra uzunligi bo’yicha o’sish tartibida tartiblangan. E ro’yxati ko’rib chiqiladi va undan maksimal uzunlikdagi qirra tanlanadi, u hali hosil bo’lgan daraxtga kiritilmagan va allaqachon qurilgan qirralari bilan siklni tashkil qilmaydi. Agar barcha uchlari daraxtga kiritilgan bo’lsa va qirralarning soni uchlari sonidan bitta kam bo’lsa, algoritm o’z ishini tugatdi. Aks holda, 3-bandga qayting. Kraskal algoritmini tushunish uchun quyidagi misolni ko’rib chiqamiz - 1-qadam - Barcha halqalarni va parallel qirralarni olib tashlang Berilgan grafdan barcha halqalarni va parallel qirralarni olib tashlang. Parallel qirralar bo’lsa, eng kam xarajatga ega bo’lganini saqlang va qolganlarini olib tashlang. 13 2-qadam - Barcha qirralarning og’irlik ortib borayotgan tartibida joylashtiring Keyingi qadam, qirralar va og’irliklar to’plamini yaratish va ularni og’irlik (narx) bo’yicha o’sish tartibida joylashtirishdir. 3- qadam - Eng kam vaznga ega bo ’ lgan qirrani qo ’ shing Endi biz eng kichik vaznga ega bo ’ lganidan boshlab grafga qirralarni qo ’ shishni boshlaymiz . Butun vaqt davomida biz oraliq xususiyatlarining buzilmaganligini tekshirishda davom etamiz. Agar bitta qirra qo’shilganda, oraliq daraxt xususiyati mos kelmasa, biz qirrani grafga kiritmaslikni ko’rib chiqamiz. Eng kam xarajat 2 va B, D va D, T bilan bog’liq qirralar. Biz ularni qo’shamiz. Ularni qo’shish keng tarqalgan daraxt xususiyatlarini buzmaydi, shuning uchun biz keyingi qirra tanlovimizni davom ettiramiz. Keyingi xarajat - 3 va bog’langan qirralar A, C va C, D. Biz ularni yana qo’shamiz - 14 Jadvaldagi keyingi xarajat 4 ga teng va biz uni qo’shish grafda sxema hosil qilishini kuzatamiz. Biz buni e’tiborsiz qoldiramiz. Bu jarayonda biz kontaktlarning zanglashiga olib keladigan barcha qirralarni e’tiborsiz qoldiramiz qirralab o’tamiz. 5 va 6 qiymatiga ega bo’lgan qirralarning ham sxemalar hosil qilishini kuzatamiz. Biz ularga e’tibor bermaymiz va davom etamiz. 15 Endi bizda faqat bitta tugun qo’shilishi kerak. Mavjud bo’lgan 7 va 8 ikkita eng kam xarajat qirralari o’rtasida biz 7 narxiga ega qirrani qo’shamiz. S, A qirralarini qo’shish orqali biz grafning barcha tugunlarini o’z ichiga oldik va endi biz minimal xarajatlarni qamrab oluvchi daraxtga egamiz. Shu bilan Kraskal algoritmi o ’ z ishini yakunlaydi . Algoritmning psevdokodi. Kraskal psevdokodi juda oson tushunarsiz kod deb atash mumkin. Axir, agar bu juda aniq bo’lsa, nima uchun barcha sharhlar satrlari? Mening fikrimcha, sof Python-dan foydalanish foydaliroq matn bo’ladi (sof aytganda, uchinchi tomon kutubxonalari kerak emas). Misol uchun, quyidagi ommaviy domen qidiruvi (Guido tomonidan) hech qanday izohga ega emas va ko’pchilik o’quvchilar uchun tushunarli bo’lishi kerak. def find_path (graph, start, end, path = []): path = path + [start] if start == end: return path if not graph.has_key(start): return None for node in graph[start]: if node not in path: 16 newpath = find_path (graph, node, end, path) if newpath: return newpath return None Agar men klasterdan fo ydalanishni va har bir tugun uchun klasterlarni birlashtirgandan keyin qaysi tugunga tayinlanishi kerakligini aniqlay olsam, uni Pythonga qo’yishga harakat qilgan bo’lardim. Shu bilan bir qatorda, bu yuqoridagi qidiruvdan foydalangan holda mening taklifim bo’ladi. def Kraskal(graph): tree = {} nodes=node_list(graph) n=len(nodes) edges = graph. Keys () edges. Sort (key=lambda x:graph[x][2]) for e in edges: v=graph[e] loop=find_path (tree, v[1], v[0]) if not loop: tree[e]=v if len(tree)>n-2: break return tree Quyidagi kod ajratilgan ma’lumotlar tuzilmasi bilan amalga oshiriladi. Bu erda biz F o’rmonimizni qirralar to’plami sifatida ko’rsatamiz va ikkita tugun bir 17 daraxtning bir qismi ekanligini samarali aniqlash uchun ajratilgan ma’lumotlar strukturasidan foydalanamiz. algorithm Kraskal( 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 Har qanday minimal kengaytm ali daraxt algoritmi qirra qo’shish halqa hosil qiladimi yoki yo’qligini tekshirish atrofida aylanadi. Buni aniqlashning eng keng tarqalgan usuli Union FInd deb nomlangan algoritmdir. Union-Find algoritmi tugunlarni klasterlarga ajratadi va bizga ikkita tugun bir xil klasterga tegishli yoki yo’qligini tekshirishga imkon beradi va shuning uchun qirra qo’shish sikl hosil qiladimi yoki yo’qligini hal qiladi. KRASKAL(G): A = ∅ For each vertex v ∈ G.V: MAKE- SET (v) For each edge (u, v) ∈ G.E ordered by increasing order by weight(u, v): if FIND- SET (u) ≠ FIND- SET (v): A = A ∪ {(u, v)} UNION (u, v) return A Algoritmning psevdokodi Qirralarni og’irliklarning o’sish tartibida tartiblang 18 ajratilgan strukturani ishga tushiring edgeCount=l esa edgeCount<=E va includeCount<=M-l do parentl=FindRoot (qirra [edgeCount]. start) = FindRoot (qirra [edgeCount]. end)parentl/=parent2 keyin qirra [edgeCount] ni kengaytmali daraxtga qo’shing = includedCount = l (parent1,parent2) if = edgeCount + l while - grafdagi qirralarning soni; V - grafdagi uchlari soni edgeCount - o’zgaruvchi; includeCount - o’zgaruvchi; - biz ishlamoqchi bo’lgan to’plamning har bir elementi uchun bitta katak ajratilgan massiv; FindRoot (x) - (x - biz uni o’z ichiga olgan qismning ildizini topmoqchi bo’lgan element) x elementining bevosita ajdodining raqamini saqlaydigan Ota [x] katakchasidan boshlanadigan protsedura; - a ikki qismning birlashmasini bajaradigan funksiya. 19 Kraskalning minimal kengayuvchi daraxt algoritmi. Kraskal algoritmidan foydalanishning asosiy maqsadi graf uchun minimal xarajat daraxtini olishdir. Biroq, agar siz minimal kenglikdagi daraxt nima ekanligini tushunmasangiz, bu mantiqiy emas. Bu misol bilan eng yaxshi tushuntirish bo’lishi mumkin. Aytaylik, bizda shunday graf bor: Bizda to’rtta tugun bor, A, B, C va D. Biz sikllarni olib tashlash va daraxt hosil qilish uchun grafning turli qirralarini o’zgartirishimiz mumkin. Bu bir necha usul bilan amalga oshirilishi mumkin: 20 Bu holda daraxtning vazni 22+21+13=56 ga teng. 21 Bu holda daraxtning vazni 10+22+21=53 ga teng. Bu holda daraxtning vazni 10+18+13=41 ga teng. Ehtiyotkorlik bilan solishtirsak, bu daraxt barcha olingan daraxtlar orasida minimal vaznga ega ekanligini ko’rishimiz mumkin. Kraskal algoritmining asosiy maqsadi ushbu minimal kenglikdagi daraxtni olishdir. Qirralarning og’irliklarining yig’indisi minimal bo’lgan grafdan olingan daraxt minimal kengayuvchi daraxt deyiladi. Minimal kengayuvchi daraxt bu bog’langan va yo’naltirilmagan graf berilgan bo’lsa, ushbu grafning kengayuvchi daraxti daraxt bo’lgan va barcha tugunlarni bir-biriga bog’laydigan pastki grafdir. Bitta grafda juda ko’p turli xil daraxtlar bo’lishi mumkin. Og’irlangan , bog’langan, yo’naltirilmagan graf uchun minimal oraliq daraxti (MOD) yoki minimal og’irlik oralig’i daraxti og’irligi har bir boshqa kengayuvchi daraxtning og’irligidan kam yoki teng bo’lgan kengayuvchi daraxtdir. Yostiqli daraxtning og’irligi - bu daraxtning yig’indisi. Minimal kenglikdagi daraxtning nechta qirrasi bor? Minimal kenglikdagi daraxtning (V - 1) qirralari bor, bu erda V - berilgan grafdagi tugunlar soni. 22 Quyida Kraskal algoritmi yordamida MOD ni topish bosqichlari keltirilgan 1. Barcha qirralarni og’irligining kamaymaydigan tartibida tartiblang. 2. Eng kichik qirraini tanlang. Hozirgacha hosil bo’lgan oraliq daraxt bilan sikl hosil qilishini tekshiring. Agar sikl hosil bo’lmasa, bu qirra qo’shing. Aks holda, uni tashlang. 3. 2-bosqichni o’tish daraxtida (V-1) qirralar paydo bo’lguncha takrorlang. 2-qadam sikllarni aniqlash uchun Union-Find algoritmidan foydalanadi. Shuning uchun biz old shart sifatida quyidagi postni o’qishni tavsiya qilamiz. Birlashma-topish algoritmi 1-to’plam (Grafdagi siklni aniqlash) Birlashma-topish algoritmi 2-to’plam (Rank va yo’l bo’yicha siqilish) Algoritm greedy algoritmdir. Greedylik tanlovi hozirgacha qurilgan MODda siklga olib kelmaydigan eng kichik og’irlik chegarasini tanlashdir. Keling, buni misol bilan tushunamiz: Quyidagi kirish grafigini ko’rib chiqing. Grafda 9 ta tugun va 14 ta burchak mavjud. Shunday qilib, hosil bo’lgan minimal kenglikdagi daraxt (9 - 1) = 8 qirraga ega bo’ladi. Saralashdan keyin: Og’irligi Src Dest 1 7 6 2 8 2 23 2 6 5 4 0 1 4 2 5 6 8 6 7 2 3 7 7 8 8 0 7 8 1 2 9 3 4 10 5 4 11 1 7 14 35 Endi qirralarning saralangan ro’yxatidan barcha qirralarni birma-bir tanlang 1. 7-6 qirraini tanlang: Hech qanday sikl hosil bo’lmaydi, uni qo’shing. 2. Pick qirrasi 8-2: Hech qanday sikl hosil bo’lmaydi, uni qo’shing. 24 3. Pick qirrasi 6-5: Hech qanday sikl hosil bo’lmaydi, uni qo’shing. 4. Pick qirrasi 0-1: Hech qanday sikl hosil bo’lmaydi, uni qo’shing. 5. Pick qirrasi 2-5: Hech qanday sikl hosil bo’lmaydi, uni qo’shing. 6. 8-6-chi qirralarni tanlang: Ushbu qirra qo’shilishi siklga olib kelganligi sababli, uni tashlang. 25 7. Pick qirrasi 2-3: Hech qanday sikl hosil bo’lmaydi, uni qo’shing. 8. 7-8 qirrani tanlang: Ushbu qirra qo’shilishi siklga olib kelganligi sababli, uni tashlang. 9. Pick qirrasi 0-7: Hech qanday sikl hosil bo’lmaydi, uni qo’shing. 10. 1-2 qirraini tanlang: Ushbu qirra qo’shilishi siklga olib kelganligi sababli, uni tashlang. 11. Pick qirrasi 3-4: Hech qanday sikl hosil bo’lmaydi, uni qo’shing. 26 Kiritilgan qirralarning soni (V - 1) teng bo’lganligi sababli, algoritm shu erda to’xtaydi. Kraskalning minimal xarajat daraxtini topish algoritmi greedy yondashuvdan foydalanadi. Ushbu algoritm grafni o’rmon va har bir tugunni alohida daraxt sifatida ko’rib chiqadi. Daraxt boshqasiga ulanadi, agar u barcha mavjud variantlar orasida eng kam xarajatga ega bo’lsa va MOD xususiyatlarini buzmasa. Og’irligi yo’naltirilmagan graf berilgan. Ushbu grafning barcha uchlarini bir-biriga bog’laydigan va shu bilan birga barcha mumkin bo’lganlarning eng kichik og’irligiga (ya’ni qirra og’irliklar yig’indisiga) ega bo’lgan shunday pastki daraxtini topish talab qilinadi. Bunday pastki daraxt minimal kenglikdagi daraxt yoki oddiy minimal kenglikdagi daraxt deb ataladi. Bu erda biz minimal kenglikdagi daraxtlar bilan bog’liq bir nechta muhim faktlarni ko’rib chiqamiz, keyin biz Kraskal algoritmini eng oddiy amalga oshirishda ko’rib chiqamiz. Minimal oraliq xususiyatlar  Agar barcha qirralarning og’irligi har xil bo’lsa, minimal kenglik daraxti noyobdir . Aks holda, bir nechta minimal oraliqlar bo’lishi mumkin (konkret algoritmlar odatda mumkin bo’lgan oraliqlardan biri bilan yakunlanadi).  Minimal skelet ham qirra og’irliklarining minimal mahsulotiga ega bo’lgan skeletdir. (buni isbotlash oson, barcha qirralarning og’irliklarini ularning logarifmlari bilan almashtirish kifoya)  Minimal skelet, shuningdek, eng og’ir qirraining minimal og’irligi bo’lgan skeletdir . (bu bayonot Kraskal algoritmining haqiqiyligidan kelib chiqadi)  Maksimal og’irlikdagi skelet minimal og’irlikdagi skeletga o’xshash tarzda qidiriladi, barcha qirralarning belgilarini qarama-qarshi tomonlarga o’zgartirish va skeletning minimal algoritmlaridan birini bajarish kifoya. 27  Eng oddiy amalga oshirish Algoritmning amaliy qismi. Kraskal algoritmida biz eng kam og’irlikdagi qirralardan boshlaymiz va maqsadga erishilgunga qadar qirralarni qo’shishni davom ettiramiz. Kraskal algoritmini amalga oshirish bosqichlari quyidagilardan iborat: o Birinchidan, barcha qirralarni past og’irlikdan balandgacha tartiblang. o Endi, eng kam og’irlikdagi qirrasini oling va uni yoyilgan daraxtga qo’shing. Agar qo’shiladigan qirra sikl yaratsa, qirradan voz keching. o Biz barcha tugunlarga yetguncha qirralarni qo’shishni davom eting va minimal kenglikdagi daraxt yaratiladi. Kraskal algoritmining ilovalari - o Kraskal algoritmi shaharlar orasidagi elektr simlarini joylashtirish uchun ishlatilishi mumkin. o U LAN ulanishlarini o’rnatish uchun ishlatilishi mumkin. Kraskal algoritmiga misol. Keling, misol yordamida Kraskal algoritmining ishlashini ko’rib chiqaylik. Misol yordamida Kraskalning algoritmini tushunish osonroq bo’ladi. Aytaylik, vaznli graf - 28 Yuqoridagi grafning qirralarining og’irligi quyidagi jadvalda berilgan - Qirra AB AC AD AE Miloddan avvalgi CD DE Og’irligi 1 7 10 5 3 4 2 Endi yuqorida keltirilgan qirralarni og’irliklarining o’sish tartibida tartiblang. Qirra AB DE Miloddan avvalgi CD AE AC AD Og’irligi 1 2 3 4 5 7 10 Keling, minimal kenglikdagi daraxtni qurishni boshlaylik. 1-qadam - Birinchidan, MODga og’irligi 1 bo’lgan AB qirraini qo’shing. 29 2-qadam - MOD ga og’irligi 2 bo’lgan DE qirrasini qo’shing, chunki u siklni yaratmaydi. 3-qadam - MOD ga og’irligi 3 bo’lgan BC qirraini qo’shing, chunki u hech qanday sikl yoki halqa yaratmaydi. 30 4-qadam - Endi MOD ga og’irligi 4 bo’lgan qirra diskni tanlang, chunki u siklni tashkil etmaydi. 5-qadam - Shundan so’ng, og’irligi 5 bo’lgan AE qirrasini tanlang. Ushbu qirra, shu jumladan, sikl hosil qiladi, shuning uchun uni tashlang. 6-qadam - Og’irligi 7 bo’lgan AC qirraini tanlang. Ushbu qirra qo’shilishi siklni yaratadi, shuning uchun uni tashlang. 7-qadam – 10 og’irligi bo’lgan AD qirrasini tanlang. Bu qirra qo’shilganda sikl ham hosil bo’ladi, shuning uchun uni tashlab yuboring. 31 Shunday qilib, Kraskal algoritmidan foydalangan holda berilgan vaznli grafdan olingan yakuniy minimal chegara daraxti - MOD narxi = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10. Endi, yuqoridagi daraxtning qirralari soni minus 1 tugunlar soniga teng. Shunday qilib, algoritm shu erda to’xtaydi. Algoritm 1. 1 - qadam: F o rmonini shunday yaratingki, grafning har bir cho qqisi alohidaʻ ʻ daraxt bo lsin. ʻ 2. 2 - qadam: Grafning barcha qirralarini o’z ichiga olgan E to’plamini yarating. 3. 3 - qadam: 4 va 5 - qadamlarni takrorlang , E BO’SH EMAS va F oraliq emas 4. 4 - qadam: Minimal og’irlik bilan E ning qirraini olib tashlang 5. 5 - qadam: Agar 4 -bosqichda olingan qirra ikki xil daraxtni bog’lasa, uni F o’rmoniga qo’shing. 6. (ikkita daraxtni bitta daraxtga birlashtirish uchun). 7. BOSHQA 8. Qirraini tashlang 9. 6- qadam: TUGASH Kraskal algoritmi uchun C++ dasturi 32 Kraskal algoritmining C++ tilida union-find algoritmi yordamida amalga oshirilishi quyida keltirilgan. Bu C++ Kraskal algoritmining manba kodi: #include <iostream> #include <vector> #include <algorithm> using namespace std; const int MAX = 1e6 - 1 ; int root[MAX]; const int nodes = 4 , edges = 5 ; pair < long long , pair < int , int > > p[MAX]; int parent( int a) // berilgan tugunning ota-onasini toping { while (root[a] != a) { root[a] = root[root[a]]; a = root[a]; } return a; } void union_find( int a, int b) // berilgan ikkita tugun bir xil "birlashmada" yoki yo'qligini tekshiring { int d = parent(a); int e = parent(b); root[d] = root[e]; } 33 long long Kraskal() { int a, b; long long cost, minCost = 0 ; for ( int i = 0 ; i < edges ; ++ i) { a = p[i] . second . first; b = p[i] . second . second; cost = p[i] . first; if (parent(a) != parent(b)) // faqat qirrani tanlang, agar u sikl yaratmasa (ya'ni, uni tashkil etuvchi ikkita tugun turli xil ildiz tugunlariga ega) { minCost += cost; union_find(a, b); } } return minCost; } int main() { int x, y; long long weight, cost, minCost; for ( int i = 0 ;i < MAX; ++ i) // massiv guruhlarini ishga tushiring { root[i] = i; } p[ 0 ] = make_pair( 10 , make_pair( 0 , 1 )); p[ 1 ] = make_pair( 18 , make_pair( 1 , 2 )); 34 p[ 2 ] = make_pair( 13 , make_pair( 2 , 3 )); p[ 3 ] = make_pair( 21 , make_pair( 0 , 2 )); p[ 4 ] = make_pair( 22 , make_pair( 1 , 3 )); sort(p, p + edges); // qirralarning qatorini tartiblang minCost = Kraskal(); cout << "Minimum cost is: " << minCost << endl; return 0 ; } Kraskal algoritmining murakkabligi. Keling, Kraskal algoritmining vaqt murakkabligini ko’rib chiqaylik. 1. #include <iostream> 2. #include <algorithm> 3. using namespace std; 4. const int MAX = 1e4 + 5; 5. int id [MAX], nodes, edges; 6. pair < long long , pair< int , int > > p[MAX]; 7. void init () 8. { 9. for ( int i = 0; i < MAX; ++i) 10. id[i] = i; 11. } 12. int root ( int x) 13. { 14. while (id[x]! = x) 15. { 16. id[x] = id[id[x]]; 17. x = id[x]; 18. } 35 19. return x; 20. } 21. void union1( int x, int y) 22. { 23. int p = root(x); 24. int q = root(y); 25. id[p] = id[q]; 26. } 27. long long Kraskal (pair< long long , pair< int , int > > p[]) 28. { 29. int x, y; 30. long long cost, minimumCost = 0; 31. for ( int i = 0;i < edges;++i) 32. { 33. x = p[i].second.first; 34. y = p[i].second.second; 35. cost = p[i].first; 36. if (root(x) != root(y)) 37. { 38. minimumCost += cost; 39. union1(x, y); 40. } 41. } 42. return minimumCost; 43. } 44. int main () 45. { 46. int x, y; 47. long long weight, cost, minimumCost; 48. Init (); 36 49. cout << "Enter Nodes and edges" ; 50. c in >> nodes >> edges; 51. for ( int i = 0; i < edges; ++i) 52. { 53. cout<< "Enter the value of X, Y and edges" ; 54. cin>> x>> y>> weight; 55. p[i] = make_pair (weight, make_pair (x, y)); 56. } 57. s ort (p, p + edges); 58. minimumCost = Kraskal(p); 59. cout << "Minimum cost is " << minimumCost << endl; 60. return 0; 61. } Chiqish Kraskal algoritmining vaqt murakkabligi O (E logE) yoki O (V logV), bu erda E - qirralarning soni, V esa - uchlari soni. 37 Vaqt murakkabligi: O(ElogE) yoki O(ElogV). Qirralarni saralash O(ELogE) vaqtni oladi. Saralashdan so’ng biz barcha qirralarni takrorlaymiz va union-find algoritmini qo’llaymiz. Topish va birlashtirish operatsiyalari eng ko’p O(LogV) vaqtni olishi mumkin. Shunday qilib, umumiy murakkablik O (ELogE + ELogV) vaqtidir. E qiymati ko’pi bilan O (V 2 ) bo’lishi mumkin, shuning uchun O(LogV) O(LogE) bir xil bo’ladi. Shuning uchun umumiy vaqt murakkabligi O(ElogE) yoki O(ElogV) ga teng. 38 39 Xulosa. Xulosa o’rnida shuni aytish mumkinki, graflar dasturlashning yangi boshlanuvchilar uchun eng qiyin sohalaridan biri hisoblanadi. Buning sababi, birinchi navbatda, graflardagi ma’lumotlar tuzilmalari va algoritmlari haqidagi savollar yechimni qanday davom ettirish haqida juda aniq emas. Faqat qattiq amaliyot orqali algoritm bo’yicha bilimlarini oshirish mumkin. Ko’rinib turibdiki, graflar bilan ishlatiladigan eng mashhur algoritmlardan biri bu grafni minimal vaqt ichida kesib o’tish va undan minimal o’tish daraxtini ishlab chiqaradigan algoritmlardir. Graflarni o’tkazish uchun minimal oraliq daraxtni Kraskal algoritmi yordamida ishlab chiqarish mumkin. Bu muammolarni hal qilish uchun graflardan foydalanganda o’rganish mumkin bo’lgan eng oson algoritmlardan biridir. Minimal kenglikdagi daraxtlar qirralarning sonini katta darajada kamaytirishga yordam beradi, shunda faqat minimal qirralar ko’rsatiladi. Bu, o’z navbatida, graflar yordamida yechilishi mumkin bo’lgan turli xil savollarni yechishda qo’llaniladi. Har qanday yangi boshlanuvchilar uchun haqiqiy qiyinchilik - graflardan muammoning yechimini topishda foydalanish mumkinligini tushunish va ularning ustunlari va qirralarini o’z foydasiga qanday boshqarishni tushunishdir. Biz ko’rib chiqqan kraskal algoritmi minimal oraliq daraxtini topish uchun qo’llaniladi.Bu algoritm greedy sifatida tanilgan.Bu algoritmning ishlash prinspi prima algoritmidan farqli o’laroq tugunni tanlash emas, balki eng kichik vaznli qirra(ya’ni yoy) ni tanlab, daraxtga qo’shish orqali amalga oshiriladi.Qirra qo’shish jarayonida bitta narsaga e’tibor berish kerak, ya’ni qo’shilgan qirra daraxtda sikl paydo qilmaslik kerak.Bu jarayon barcha tugunlar o’zaro bog’langunga qadar davom etadi.Kraskal algoritmi shaharlararo elektr liniyalarini o’rnatishda ishlatiladi. 40 Foydanilgan adabiyotlar. 1.M.O’. ASHUROV, SH.A.SATTAROVA, SH.U.USMONQULOV, „ALGORITMLAR“, «Fan va texnologiya» nashriyoti, 2018. 2.H.To‘rayev,“Kombinatorika va graflar nazariyasi”, “Ilm ziyo”, 2009, 3.Akbaraliyev B.B., Yusupova Z.Dj, “MA LUMOTLAR TUZILMASI VA‟ ALGORITMLAR”, Toshkent 2013 4.Toirov Sh.A., Raximov R.T., Karimov M.M, “ALGORITMGA KIRISH” fanidan laboratoriya ishlarini bajarish bo’yicha USLUBIY KO’RSATMA”, Samarqand 2015 5.Xayitmatov O‘.T, Inogomjonov E.E., Sharipov B.A., Ro’zmetova N., Rahimboboeva D,” MA’LUMOTLAR TUZILMASI VA ALGORITMLARI”, Toshkent – 2011 6.Л.И.Домнин, “ЭЛИМЕНТЫ ТЕОРИИ ГРАФОВ”, “Пенза Издательство Пензенского государственного университета“,2007 7.Никлаус Вирт,”Алгоритмы и структуры данных Новая версия для Оберона +CD“, Москва ,2010 Foydalanilgan internet saytlar 8.https://kursovik.com/programming/320372.html 9.http://aliev.me/runestone/Graphs/PrimsSpanningTreeAlgorithm.html 10.http://www.hpcc.unn.ru/?dir=836 11.https://brestprog.by/topics/MOD/ 12. https://wikipedia.uz 13.https://evileg.com/ru/post/524/ 14.http://www.mkurnosov.net/ 41 42

“KRASKAL ALGORITMI” MAVZUSIDA TAYYORLAGAN Mundarija Kirish. ............................................................................................................................................................................. 2 Kraskal algoritmi. ............................................................................................................................................................ 3 Kraskal algoritmining tavsifi. ......................................................................................................................................... 7 Algoritmning psevdokodi. ............................................................................................................................................ 16 Kraskalning minimal kengayuvchi daraxt algoritmi. .................................................................................................... 20 Algoritmning amaliy qismi. .......................................................................................................................................... 28 Kraskal algoritmining murakkabligi. ............................................................................................................................ 35 Xulosa. .......................................................................................................................................................................... 40 Foydanilgan adabiyotlar. ............................................................................................................................................... 41 1

Kirish. Kurs ishining o’rganish ob’ekti Kraskal algoritmini amalga oshirish edi. Ishning maqsadlari quyidagilar edi: 1)kraskal algoritmi, uning tarixi bilan tanishish; 2)minimal kenglikdagi daraxtni qurish algoritmini amalga oshirish; 3)algoritmning murakkabligini tahlil qilish; 4)algoritmni sinash. Bog’langan vaznli grafning minimal oraliq daraxti (MOD) uning bog’langan pastki grafigi bo’lib, u asl daraxtning barcha uchlari va uning ba’zi qirralaridan iborat bo’lib, qirralarning og’irliklarining yig’indisi maksimal mumkin. Agar asl graf uzilgan bo’lsa, unda quyida tavsiflangan protsedura uning har bir ulangan komponentiga navbat bilan qo’llanilishi mumkin va shu bilan ushbu komponentlar uchun minimal oraliq daraxtlarni olish mumkin. Kraskal algoritmi (yoki Kraskal algoritmi) vaznli bog langan yo naltirilmagan graf uchun minimal oraliqli daraxtniʻ ʻ qurish algoritmidir. Algoritm birinchi marta 1956 yilda Jozef Kraskal tomonidan tasvirlangan. Kraskal algoritmi bir vaqtning o’zida bir nechta bog’langan komponentlar uchun daraxt qurishi mumkin, ular hal qilish jarayonida bitta bog’langan daraxtga birlashtiriladi. To’liq graf qirralarning ro’yxati bilan berilgan. Yugurishdan oldin qirralarning ro’yxati uzunlik bo’yicha o’sish tartibida tartiblanadi. Har bir bosqichda qirralarning ro’yxati ko’rib chiqiladi, oldingi bosqichdagi yechimga kiritilganidan keyingi qirraidan boshlab, eritma ichiga kiritilgan qirralar bilan sikl hosil qilmaydigan qirra pastki daraxtga qo’shiladi. qurilish ishlari olib borilmoqda. Daraxtning minimal uzunligini topish muammosi ko’pincha shunga o’xshash sharoitda yuzaga keladi: n ta shahar bor, ular orqali siz istalgan shahardan boshqasiga (to’g’ridan-to’g’ri yoki boshqa shaharlar orqali) borishingiz mumkin bo’lgan marshrutni yotqizishingiz mumkin. Yo’l haqi maksimal bo’lishi uchun shunday marshrutni topish talab qilinadi. Amalda Kraskal 2

algoritmi aviakompaniyalar tomonidan bir yo’nalishdan ikkinchisiga eng qisqa havo yo’lini topishda qo’llaniladi. Kraskal algoritmi. Kraskal algoritmi bog’langan vaznli graf uchun minimal oraliq daraxtini topish uchun ishlatiladi. Algoritmning asosiy maqsadi biz grafning har bir tugunini kesib o’tishimiz mumkin bo’lgan qirralarning pastki to’plamini topishdir. U global optimalga e’tibor qaratish o’rniga har bir bosqichda optimal echim topadigan greedy yondashuvga amal qiladi. Kraskal algoritmi bu grafning MODni topish uchun boshqa mantiqdan foydalanadigan yana bir mashhur minimal oraliqli daraxt algoritmi. Kraskal algoritmi tugundan boshlash o’rniga, barcha qirralarni past og’irlikdan yuqoriga saralaydi va siklni yaratadigan qirralarga e’tibor bermasdan, eng past qirralarni qo’shishda davom etadi. Kraskal algoritmi dastlab har bir tugunni o’z daraxtiga joylashtiradi, so’ngra bu daraxtlarni asta-sekin birlashtirib, har bir iteratsiyada qaysidir qirrada ikkita ma’lum daraxtni birlashtiradi. Algoritmni boshlashdan oldin barcha qirralarning vazni bo’yicha (kamaymaslik tartibida) tartiblanadi. Keyin birlashtirish jarayoni boshlanadi: barcha qirralar birinchisidan oxirgisiga (tartib tartibida) o’tkaziladi va agar joriy qirraning uchlari turli pastki daraxtlarga tegishli bo’lsa, u holda bu pastki daraxtlar birlashtiriladi va javobga qirra qo’shiladi. Barcha qirralarni sanab o’tish oxirida barcha tugunliklar bir xil pastki daraxtga tegishli bo’ladi va javob topiladi. Bizda quyidagi yo’naltirilmagan vaznli graf mavjud, grafning barcha tugunlarini o’z ichiga olgan pastki graf, ya’ni daraxt bo’lgan kengaytmali daraxt deb ataymiz va vazifa - qirralarining yig’indisi minimal bo’lgan bunday kengaygan daraxtni topishdir. Asl grafni qirralarsiz tasavvur qiling, endi siz barcha tugunlarni qandaydir tarzda bir-biriga bog’lashingiz kerak, shunda siz istalgan tugundan ikkinchisiga 3

o’tishingiz mumkin, natijada olingan grafda kiritilgan qirralarning og’irliklarining minimal mumkin bo’lgan yig’indisi bilan sikllarsiz ishlaydi. Ushbu algoritmning ishlash mexanizmi juda oddiy. Kirish qismida bo’sh subgraf mavjud bo’lib, biz uni potentsial minimal kenglikdagi daraxtga yakunlaymiz. Biz faqat bog’langan graflarni ko’rib chiqamiz, aks holda Kraskal algoritmini qo’llashda biz minimal kenglikdagi daraxtni emas, balki oddiygina o’rmonni olamiz.  Birinchidan, biz qirralarni og’irliklari bo’yicha kamaymaydigan tartibda saralaymiz.  Biz subgrafimizga qirra qo’shamiz i- ое , agar bu qirra ikki xil bog’langan komponentni bog’lasa, ulardan biri bizning subgrafimizdir. Ya’ni, har bir qadamda minimal og’irlik qirrasi qo’shiladi, uning bir uchi bizning subgrafimizda mavjud, ikkinchisi esa hali yo’q.  Algoritm o’z ishini subgrafimizning tugunlari to’plami asl grafning tugunlari to’plamiga to’g’ri kelgandan keyin yakunlaydi. Ushbu algoritm greedy deb ataladi, chunki har bir qadamda biz umuman optimal yechimga olib keladigan eng yaxshi variantni topishga harakat qilamiz. Muayyan misolni bosqichma-bosqich tahlil qilish. Quyda keltirilgan grafdan biz uning barcha qirralarini tartiblangan tartibda yozamiz, va biz ushbu qirralarni ro’yxatdagi skeletimizga qo’shishni boshlaymiz: 1) D <--> B; w = 2 2) D <--> C; w = 6 4

3) A <--> B; w = 7 4) A <--> C; w = 8 5) C <--> E; w = 9 6) D <--> F; w = 9 7) F <--> E; w = 10 8) B <--> C; w = 11 9) D <--> E; w = 11 1-qirra qo’shgandan keyin pastki chiziq 2 va 3 qirralarni qo’shgandan so’ng subgraph A <--> C Ko’rib turganingizdek, bizning kengaygan daraxtimizga qirra qo’shsangiz, sikl hosil bo’ladi, shuning uchun biz bu qirrani o’tkazib yuboramiz. Natijada, bizda quyidagi subgraf bor va siz sezganingizdek, biz barcha tugunlarni qirralar bilan minimal mumkin bo’lgan og’irliklar bilan birlashtirdik, ya’ni biz asl grafmiz uchun minimal oraliq daraxtini topdik. 5

Похожие

Deykstra Algoritmi
Timsort saralash algoritmi
Shiber-vishkin algoritmi
Xon saralash algoritmi
Oriyentatsiya funksiyasi. Grexem algoritmi. Ajrat va hukmron bo`l algoritmi