Telekommunikatsiya va kommunikatsiyalarni rivolantirish vazirligi

Union FInd algoritmidir 
. Union-Find algoritmi cho'qqilarni klasterlarga 
ajratadi va bizga ikkita cho'qqi bir xil klasterga tegishli yoki yo'qligin i tekshirishga 
imkon beradi va shuning uchun chekka qo'shish sikl hosil qiladimi yoki yo'qligini hal 
qiladi. 
1.
KRUSKAL(G):( G ): 
2.
A = 
∅
3.
Har bir tepalik uchun v 
∈
G . V : 
4.
MAKE - SET ( v ) 
5.
Har bir chekka uchun ( u , v ) 
∈
G . E vazn bo'yicha tartibni oshirish orqali 
tartiblangan ( u , v ):

---

6.
agar FIND - SET ( u ) ≠ FIND - SET ( v ):
7.
A = A 
∪
{( u , v )}
8.
UNION ( u , v ) 
9.
qaytish A 
Kraskal algoritmi Primaga qarshi 
Prim algoritmi MST grafigini topish uchun boshqa mantiqdan foydalanadigan yana 
bir mashhur minimal oraliqli daraxt algoritmidir. Prim algoritmi chekkadan boshlash 
o'rniga, cho'qqidan boshlanadi va barcha cho'qqilar qoplanmaguncha daraxtda 
bo'lmagan eng kichik og'irlikdagi qirralarni qo'shishda davom etadi. 
Faraz qilamiz, V = {1, 2, .... n} bo’g’imlar to’plamidan iborat va Ye qirralar 
to’plamida aniqlangan s narx funksiyasi bilan berilgan G=(V, Ye) bog’langan graf 
bo’lsin. Kruskal algoritmida G graf uchun minimal narxli daraxtlar skletini qurish G 
grafning faqat n ta bo’g’imlaridan tashkil topgan va qirralari bo’lmagan T=(V, ø) 
grafdan boshlanadi. Shunday qilib, har bir bo’g’im bog’langan (o’zi-o’zi bilan) 
komponent hisoblanadi. Algoritm bajarilishi vaqtida bog’langan komponentlar 
naboriga ega bo’lamiz, asta-sekin
 
birlashtirib
 
daraxtlar skletini tashkillashtiramiz. 
 
Asta-sekin o’suvchi bog’langan komponentlarni qurishda Ye to’plamdan qirralar 
ularning narxi o’sishi tartibida navbatma-navbat tekshiriladi. Agar navbatdagi qirra
 
turli 
komponentlardagi ikkita bo’g’imni birlashtirsa, u holda bu qirra T grafga qo’shiladi. 
Agar bu qirra bitta komponentning ikkita bo’g’imini birlashtirsa, u tashlab yuboriladi, 
chunki uning bog’langan komponentga qo’shilishi sikl hosil bo’lishiga olib keladi. G 
grafning barcha bo’g’imlari bitta komponentga tegishli bo’lsa, T minimal narxli 
daraxtlar skletini qurish bu graf uchun tugaydi. Misol: 

---

 
S bog’langan komponentlar to’plami kerak, bu uchun quyidagi operatorlar 
ishlatiladi: 
1. MERGE(A, V, S) operatori S nabordan A va V bog’langan komponentlarni 
birlashtiradi va natijani A yoki V ga joylashtiradi. 
2. FIND(v, S) funksiyasi S nabordan v bo’g’imni o’z ichiga olgan komponentning 
nomini qaytaradi. 
3. INITIAL(A, v, S) operatori naborda faqat v bo’g’imdan iborat A nomli 
komponentni yaratadi. 
Ushbu algoritm