KRASKAL ALGORITMI















![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)

![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)













![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)





“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