KRASKAL ALGORITMI
![“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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_1.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_2.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_3.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_4.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_5.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_6.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_7.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_8.png)
![Dastlab, biz minimal vaznga ega bo’lgan birinchi qirrani tanlashimiz kerak. Bu
erda AB tanlanadi, uning og’irligi 10 ga teng.
9](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_9.png)
![Endi biz ikkinchi minimal og’irlik bilan qirrasini tanlaymiz. Bu erda disk og’irligi
13 bo’lgani uchun tanlanadi.
10](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_10.png)
![Keyinchalik davom etsak, minimal og’irlikdagi qirra BC ekanligini
aniqlaymiz. Ushbu qirraning og’irligi 18 ga teng.
11](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_11.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_12.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_13.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_14.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_15.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_16.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_17.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_18.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_19.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_20.png)
![Bu holda daraxtning vazni 22+21+13=56 ga teng.
21](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_21.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_22.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_23.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_24.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_25.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_26.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_27.png)
![ 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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_28.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_29.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_30.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_31.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_32.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_33.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_34.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_35.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_36.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_37.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_38.png)
![39](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_39.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_40.png)
![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](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_41.png)
![42](/data/documents/55cc56f7-da3e-4f28-b46e-f9ee17906e03/page_42.png)
“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