Mustaqil ish ­­ cal015 (415) guruh talabasi Bajardi: Bahodirov Samandar Tekshirdi: Begimov O’ktam

algorithm Kruskal(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

Foydalanilgan sayt linki:
https://fayllar.org/upload/download/id721683

Bizda quyidagi yo'naltirilmagan vaznli grafik mavjud. Asl grafaning barcha uchlarini o'z ichiga olgan pastki grafik, ya'ni daraxt bo'lgan oraliq daraxt deb ataymiz. Va vazifa - chekkalarining yig'indisi minimal bo'lgan bunday kengaygan daraxtni topishdir.

Muammoning norasmiy bayonoti
Asl grafikni qirralarsiz tasavvur qiling, endi siz barcha cho'qqilarni qandaydir tarzda bir-biriga bog'lashingiz kerak, shunda siz istalgan cho'qqidan ikkinchisiga o'z ichiga olingan qirralarning og'irliklarining minimal mumkin bo'lgan yig'indisi bilan hosil bo'lgan grafikda tsikllarsiz o'tishingiz mumkin.

Kruskal algoritmi

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 grafiklarni ko'rib chiqamiz, aks holda Kruskal algoritmini qo'llashda biz minimal kenglikdagi daraxtni emas, balki oddiygina o'rmonni olamiz.
Birinchidan, biz qirralarni og'irliklari bo'yicha kamaymaydigan tartibda saralaymiz.

Biz i-chi chekkani subgrafimizga qo'shamiz, agar bu chekka 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 cho'qqilari to'plami asl grafikning cho'qqilari to'plamiga to'g'ri kelganidan keyin yakunlaydi.

Ushbu algoritm ochko'z deb ataladi, chunki har bir qadamda biz umuman optimal echimga olib keladigan eng yaxshi variantni topishga harakat qilamiz.

Muayyan misolni bosqichma-bosqich tahlil qilish

Yuqoridagi grafikdan uning barcha qirralarini tartiblangan tartibda yozing:
1) D <--> B; w = 2
2) D <--> C; w = 6
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
Va keling, ushbu qirralarni ro'yxatga muvofiq skeletimizga qo'shishni boshlaylik:


Ko'rib turganingizdek, biz A <--> C chekkasini qo'shsak, ko'rib turganingizdek, bu chetni o'tkazib yuboramiz.

Natijada, bizda quyidagi pastki grafik mavjud va siz sezganingizdek, biz barcha cho'qqilarni qirralar bilan minimal mumkin bo'lgan og'irliklar bilan bog'ladik, ya'ni biz asl grafigimiz uchun minimal masofa daraxtini topdik.

MST ni graphonlineda topish uchun biz o'rnatilgan algoritm bilan tekshiramiz va biz subgraflar bir xil ekanligini ko'ramiz.
Va ha, agar qirralarning og'irligi teng bo'lsa, biz ulardan istalganini tanlashimiz mumkinligi sababli, minimal bo'lgan daraxtlar bo'lgan oxirgi subgraflar ba'zi qirralarga qadar farq qilishi mumkin.

Amalga oshirish
Taqdim etilgan algoritmni SNM (kesishmayotgan segmentlar tizimi) yordamida amalga oshirish eng oson.

Avval aytib o'tganimizdek, qirralarni og'irliklari bo'yicha kamaymaydigan tartibda saralash kerak. Bundan tashqari, make_set() funksiyasi chaqiruvlaridan foydalanib, biz har bir cho'qqini o'z daraxtiga joylashtirishimiz mumkin, ya'ni biz ma'lum bir subgraflar to'plamini yaratamiz. Keyin biz barcha qirralarni tartiblangan tartibda takrorlaymiz va find_set() funksiyasidan foydalangan holda joriy chekkaning tushuvchi uchlari turli subgraflarga tegishli yoki yoʻqligini koʻramiz, agar ikkala uchi ham turli komponentlarda boʻlsa, u holda ikkita turli subgraflarni bittaga birlashtiramiz. union_sets() funktsiyasi.

Natijada, ushbu algoritmning asimptotik murakkabligi quyidagicha kamayadi:
O(ElogV + V + E) = O(ElogV),
sort() - O(ElogV)
make_set()- O(V)
find_set - O(1)
union_sets - O(1)
Prim algoritmi
Prim algoritmining o'zi ham qirralarning ochko'z sanab o'tishiga to'g'ri keladi, lekin allaqachon ma'lum bir to'plamdan. Kirish qismida bo'sh subgraf ham mavjud bo'lib, biz uni potentsial minimal oraliq daraxtga yakunlaymiz. Dastlab, bizning subgrafimiz asl grafikning istalgan bir cho'qqisidan iborat.

Keyin, bu cho'qqigacha bo'lgan qirralardan ikkita mutlaqo boshqa bog'langan komponentni bog'laydigan shunday minimal chekka tanlanadi, ulardan biri bizning subgrafimizdir. Ya'ni, subgrafimizga yangi cho'qqi qo'shish imkoniga ega bo'lishimiz bilan, biz uni darhol mumkin bo'lgan minimal og'irlik bo'yicha kiritamiz.

Biz kerakli MSTni topmagunimizcha oldingi bosqichni bajarishni davom ettiramiz.
Muayyan misolni tahlil qilish
Biz tasodifiy E cho'qqini tanlaymiz, so'ngra undan chiqadigan barcha qirralarni ko'rib chiqamiz, biz C <--> E chetini o'z ichiga olamiz; w = 9, chunki bu chekka bizning subgrafimizning tepa to'plamiga tushadigan barcha qirralarning minimal og'irligiga ega. Bizda quyidagilar mavjud:

Endi tanlash qirralardan amalga oshiriladi:
D <--> C; w = 6
A <--> C; w = 8
F <--> E; w = 10
B <--> C; w = 11
D <--> E; w = 11
Ya'ni, hozirgi vaqtda biz faqat ikkita cho'qqi haqida bilamiz, mos ravishda biz ulardan chiqadigan barcha qirralar haqida bilamiz. Bizning subgrafimizga kiritilmagan boshqa tepaliklar orasidagi bog'lanishlar haqida hech narsa bilmaymiz, shuning uchun ular bu bosqichda ko'rib chiqilmaydi.

Biz subgrafimizga D <--> C chetini qo'shamiz va o'xshashlik bo'yicha D <--> B chetini qo'shamiz. Biz quyidagilarni olamiz:

Keling, subgrafimizni minimal bo'lgan daraxtga olib boraylik. Qolgan cho'qqilarni ulash uchun qaysi qirralardan foydalanishimizni allaqachon taxmin qilgan bo'lsangiz kerak:
A va F.

Biz tugatish ishlarini qo'ydik va minimal kenglikdagi daraxt bilan bir xil subgrafni oldik. Ammo yuqorida aytib o'tganimizdek, subgrafning o'zi hech narsani hal qilmaydi, bu erda asosiy narsa - bu bizning oraliq daraxtimizga kiritilgan qirralarning to'plami.

Istalgan MSTning umumiy og'irligi 33 ni tashkil qiladi.
"Bizning kenglikdagi daraxtga i-chekkani qo'shish" - Siz "qo'zg'alish daraxti" ni qayerdan olganimizni aytmaysiz (aslida, algoritm oxirida kengayuvchi daraxtga aylanadigan qisman grafik) va qanday qilib bu ishga tushiriladi.
Har safar tsikl borligini tekshirish noto'g'ri, shuning uchun 2-bandni quyidagicha qayta ta'riflash yaxshiroq bo'lar edi: "Agar u ikkita alohida bog'langan komponentni bog'lasa, G' qisman grafigiga i-chekkani qo'shing". Dastlab, G' qirralarni o'z ichiga olmaydi, ya'ni. har bir cho'qqi alohida bog'langan komponent hisoblanadi. Siz ularga raqamlar belgilashingiz va chekka qo'shganda ularni to'g'rilashingiz mumkin (biz 3 va 6 raqamlari bo'lgan A va B cho'qqilariga chekka hodisasini qo'shamiz - bu degani 3 va 6 raqamlari bo'lgan barcha cho'qqilar yangi raqam oladi, bu ikkalasi ham bo'lishi mumkin. 3 va 6, va ba'zi f (3, 6)).
Kerakli raqam o'rniga grafikning barcha qirralarini hisobga olish shunchaki amalga oshirish tafsiloti emas, balki asimptotikani sezilarli darajada yomonlashtirishning ishonchli usulidir. M cho'qqisi bo'lgan to'liq grafik m*(m-1)/2 qirralarni o'z ichiga oladi. Holbuki, m cho'qqisi bo'lgan har qanday grafikning oraliq daraxti m - 1 qirralarni o'z ichiga oladi. Shunday qilib, algoritmning aniq m - 1 qadamini bajarish kerakligi aniq (agar biz boshqacha bahslashsak, dastlab m bog'langan komponent mavjud va har bir bosqichda ikkita bog'langan komponent bittaga birlashtiriladi, bu ularning sonini 1 ga kamaytiradi) . Bular. qirralarning soni G' 0 dan m - 1 gacha o'sadi va ulangan komponentlar soni G' m dan 1 gacha kamayadi.
Umuman olganda, menimcha, algoritmlar murakkab emas va yuzaki tushunish darajasida "oling, u erga qo'shing" hamma narsa aniq
Foydalanilgan sayt linki:
https://habr.com/ru/articles/569444/
Kruskal algoritmini noldan o'rganish uchun sizning yagona yechimingiz
Ravikiran AS tomonidan
Oxirgi yangilangan: 2023-yil 16-mart126523

Mundarija
Kruskal algoritmiga kirish
Yopuvchi daraxt nima?
Minimal kenglikdagi daraxt nima? 
Minimal cho'zilgan daraxtning nechta qirrasi bor? 
Kruskal algoritmidan foydalanib, minimal kenglikdagi daraxtni yaratish
Koʻproq koʻrish
Kruskal algoritmi diskret matematikaning grafik nazariyasiga kiritilgan tushunchadir. U bog'langan vaznli grafikdagi ikkita nuqta orasidagi eng qisqa yo'lni aniqlash uchun ishlatiladi. Bu algoritm har bir tugunni alohida daraxt sifatida hisobga olgan holda berilgan grafikni o‘rmonga aylantiradi. Ushbu daraxtlar bir-biriga bog'lanishi mumkin, agar ularni bog'laydigan chekka past qiymatga ega bo'lsa va MST tuzilmasida tsikl hosil qilmasa. Ushbu qo'llanmada siz Kruskal algoritmi haqida batafsil ma'lumotga ega bo'lasiz.
Kruskal algoritmiga kirish
Yuqorida aytib o'tilganidek, Kruskal algoritmi berilgan grafik uchun minimal oraliq daraxtini yaratish uchun ishlatiladi . Biroq, minimal oraliq daraxt nima? Minimal kengayuvchi daraxt - bu grafikning uchlari soni grafik bilan bir xil bo'lgan va qirralarning -1 soniga teng bo'lgan pastki to'plami. Bundan tashqari, u kengaygan daraxtdagi barcha chekka og'irliklarining yig'indisi uchun minimal narxga ega.
Kruskal algoritmi barcha qirralarni chekka og'irliklarining ortib borish tartibida saralaydi va tanlangan chekka hech qanday sikl hosil qilmasa, daraxtga tugunlarni qo'shishda davom etadi. Bundan tashqari, u dastlab minimal xarajat bilan chekkasini va oxirida maksimal xarajat bilan chekkasini tanlaydi. Demak, Kruskal algoritmi global optimal yechimni topish niyatida mahalliy optimal tanlovni amalga oshiradi, deyishingiz mumkin. Shuning uchun u ochko'z algoritm deb ataladi. 
Asoslarni ilg'or darajaga - barchasini o'rganing!
Caltech PGP Full Stack DevelopmentO'RGANISH DASTURI

Yopuvchi daraxt nima?
Chiziqli daraxt - bu grafikning barcha cho'qqilari va asl grafaning ba'zi qirralarini o'z ichiga olgan, hech qanday sikllarga ega bo'lmaslik uchun pastki to'plami. Yopuvchi daraxt har doim ham noyob bo'lishi shart emas - berilgan grafik uchun bir nechta kengayuvchi daraxtlar bo'lishi mumkin. Biroq, berilgan grafik har doim kamida bitta kengayuvchi daraxtga ega bo'ladi. Yopiladigan daraxtning qirralari "novdalar qirralari" deb ataladi, yoyiladigan daraxtda bo'lmagan qirralar esa "tsikl qirralari" deb ataladi. Va bu turdagi grafik grafikdagi barcha cho'qqilarni ulash uchun zarur bo'lgan minimal qirralarning sonini topishga yordam beradi. Bundan tashqari, ortiqcha yo'llar bilan minimal himoyalangan tarmoqlarni yaratish uchun foydalaniladi.
Minimal kenglikdagi daraxt nima? 
Minimal kenglik daraxti (MST) - bu bog'langan, chekka og'irligi bo'lgan grafikning chekkalarining kichik to'plami bo'lib, u barcha cho'qqilarni hech qanday aylanishlarsiz va minimal mumkin bo'lgan umumiy chekka og'irligi bilan bir-biriga bog'laydi. Bu cho'qqilar to'plamini ulashning eng iqtisodiy usulini topishning bir usuli. Minimal kenglikdagi daraxt noyob bo'lishi shart emas. MSTdagi qirralarning barcha og'irliklari aniq bo'lishi kerak. Agar grafikdagi qirralarning barcha og'irliklari bir xil bo'lsa, u holda grafikning har qanday kengayuvchi daraxti MST hisoblanadi. Minimal kenglikdagi daraxtning qirralarini ochko'z algoritm yoki yanada murakkab Kruskal yoki Prim algoritmi yordamida topish mumkin.
Minimal cho'zilgan daraxtning nechta qirrasi bor? 
Minimal kengayish daraxti (MST) - bu bog'langan, yo'naltirilmagan grafikning chekkalarining kichik to'plami bo'lib, barcha cho'qqilarni qirralarning eng kam mumkin bo'lgan umumiy og'irligi bilan bog'laydi. Minimal kenglikdagi daraxt aniq n-1 qirralarga ega, bu erda n - grafikdagi cho'qqilar soni. 
Kruskal algoritmidan foydalanib, minimal kenglikdagi daraxtni yaratish
Minimal kenglikdagi daraxtni yaratish uchun avval Kruskal algoritmidagi qadamlarni ko'rib chiqasiz:

• 
  1-qadam: Barcha qirralarni chekka og'irliklarining ortib borish tartibida tartiblang.
  
• 
  2-qadam: Eng kichik chetini tanlang.
  
• 
  3-qadam: Yangi chekka kengayuvchi daraxtda tsikl yoki halqa hosil qilishini tekshiring.
  
• 
  4-qadam: Agar u tsiklni tashkil qilmasa, u holda MSTga ushbu chekka qo'shing. Aks holda, uni tashlang.
  
• 
  5-qadam: 2-bosqichdan boshlab |V|ni o'z ichiga olguncha takrorlang - MSTda 1 ta chekka.
  

Yuqorida aytib o'tilgan qadamlardan foydalanib, siz minimal kenglikdagi daraxt tuzilishini yaratasiz. Endi bu jarayonni yaxshiroq tushunish uchun misolni ko'rib chiqing.
Quyida berilgan G(V, E) grafigi 6 ta uch va 12 ta qirradan iborat. Va siz G(V, E) uchun T(V', E') minimal kengaytmali daraxt yaratasiz, shunda T dagi uchlar soni 6 va qirralari 5 (6-1) bo'ladi.

Agar siz ushbu grafikni kuzatsangiz, xuddi shu tugunni yana o'ziga bog'laydigan ikkita halqa qirralarini topasiz. Va bilasizki, daraxt tuzilishi hech qachon pastadir yoki parallel qirrani o'z ichiga olmaydi. Shunday qilib, birinchi navbatda siz ushbu qirralarni grafik tuzilmasidan olib tashlashingiz kerak bo'ladi.

Siz davom etadigan keyingi qadam, barcha qirralarni chekka og'irliklari bo'yicha tartiblangan ro'yxatda joylashtirishdir.

Grafik qirralari	Kenar og'irligi
Manba Vertex	Manzil Vertex
E	F	2
F	D	2
B	C	3
C	F	3
C	D	4
B	F	5
B	D	6
A	B	7
A	C	8

Ushbu bosqichdan so'ng siz MSTga qirralarni qo'shasiz, shunda kiritilgan chekka daraxt tuzilishida tsikl hosil qilmaydi. Siz tanlagan birinchi chekka EF chekkasidir, chunki uning eng kam og'irligi 2 ga teng.

Yopiladigan daraxtga chekka FD qo'shing.

Yopiladigan daraxtga BC chetini va CF chetini qo'shing, chunki u hech qanday halqa hosil qilmaydi

Keyingi - chekka CD. Bu chekka sizning daraxt tuzilmangizda halqa hosil qiladi. Shunday qilib, siz bu chekkadan voz kechasiz.

Edge CD dan keyin sizda chekka BF bor. Bu chekka ham pastadir hosil qiladi; shuning uchun siz uni tashlab ketasiz.

Keyingi - chekka BD. Bu chekka, shuningdek, pastadirni shakllantiradi, shuning uchun siz uni ham tashlab yuborasiz.

Sizning tartiblangan ro'yxatingizdagi keyingi AB chekkasi. Bu chekka hech qanday sikl hosil qilmaydi, shuning uchun uni MST tuzilishiga kiritish shart emas. Ushbu tugunni qo'shish orqali u MSTga 5 ta qirrani o'z ichiga oladi, shuning uchun tartiblangan ro'yxatda boshqa yo'lni bosib o'tishingiz shart emas. MST ning yakuniy tuzilishi quyidagi rasmda ko'rsatilgan:

MST T(V', E') dagi barcha chekka og'irliklarining yig'indisi 17 ga teng bo'lib, bu aniq grafik uchun mumkin bo'lgan har qanday kengayuvchi daraxt tuzilishi uchun mumkin bo'lgan eng kam chekka og'irligidir. Oldinga qarab, siz Union Find Algoritm yordamida Kruskal algoritmlarini amalga oshirish haqida bilib olasiz.