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

Union Find algoritmi nima?

Union Find - bu bitta yoki bir nechta ajratilgan to'plamga bo'lingan elementlarni kuzatib boradigan algoritm. U ikkita asosiy operatsiyaga ega: Top va Birlashma. Find operatsiyasi berilgan element (argument) tegishli bo'lgan elementlar to'plamini qaytaradi, Union operatsiyasi esa ikkita ajratilgan to'plamni birlashtiradi.
Kruskal yondashuvidan foydalangan holda, minimal kenglikdagi daraxtni qurishda taqdim etilgan G (V, E) grafigini uchta alohida to'plamga bo'lishingiz kerak. Birinchisi chekka og'irlik qiymatlarini o'z ichiga oladi, ikkinchisi aniq tugunlar uchun daraxt ierarxiyasiga ega, uchinchisi esa barcha tugunlarning darajasini o'z ichiga oladi. Birlashma va topish operatsiyalaridan foydalangan holda, u minimal kenglikdagi daraxtni shakllantirish uchun turli daraxtlar sifatida qaraladigan alohida tugunlarni birlashtiradi. 
Kruskal algoritmini amalga oshirish
Har qanday MST algoritmi chekka qo'shish tsiklga olib keladimi yoki yo'qligini aniqlash atrofida aylanadi. Union Find buni aniqlashning eng mashhur algoritmidir. Union-Find algoritmi cho'qqilarni klasterlarga ajratadi, bu sizga ikkita cho'qqi bir xil klasterga tegishli yoki yo'qligini aniqlashga imkon beradi va shuning uchun chekka qo'shish tsiklni keltirib chiqaradi.
Union-Find yordamida Kruskal algoritmini amalga oshirish strategiyasi quyida keltirilgan:

• 
  Manba va maqsad tugunlarini, shuningdek, ularning og'irligini kuzatib borish uchun strukturani tuzing.
  
• 
  Grafikning barcha qirralarini chekka og'irlik qiymatlariga ko'ra tartiblang.
  
• 
  Grafik tugunlarini, ularning daraxtdagi ierarxiyasini va har bir tugun uchun mos darajalarni saqlash uchun uchta alohida to'plam yarating.
  
• 
  Avvalo, barcha daraja qiymatlarini 0 ga va asosiy qiymatlarni -1 ga boshlang (har bir tugunni o'z daraxti sifatida ifodalaydi).
  
• 
  MST-ga chekkaning har bir kiritilishi uchun siz har bir tugunning darajasi va ota-onasini yangilaysiz.
  
• 
  Ikki tugunni bir-biriga bog'laydigan chekkasini qo'ymang, agar ular bir xil ota-tugunga ega bo'lsa, bu daraxt tuzilishidagi tsiklni keltirib chiqaradi.
  

Endi siz ushbu amalga oshirish strategiyasini misol yordamida tushunasiz. Kruskal yondashuvidan foydalangan holda siz minimal kenglikdagi daraxtni ishlab chiqadigan grafik quyida keltirilgan:

Dastlab, har bir tugun uchun asosiy qiymat va daraja qiymatini saqlash uchun ikkita to'plam yaratishingiz kerak bo'ladi. Shu bilan birga, siz grafikning chekkalarini ushlab turish uchun tuzilma yaratasiz. Grafikdagi barcha tugunlar uchun siz asosiy qiymatlarni -1 ga ishga tushirasiz va qiymatlarni 0 ga qo'yasiz. Buning sababi shundaki, siz grafikning barcha tugunlariga daraxt sifatida qarashingiz kerak.

Bundan tashqari, esda tutingki, har doim ikkita bir-biridan ajralgan daraxt tuzilmalarini birlashtirganingizda, ko'rsatilgan birining darajasi birga ko'tariladi. Shunday qilib, MSTga qirralar qo'shganingizdan so'ng, kiritilgan tugunlarning darajalari va ota-onalari o'zgaradi. Ushbu maxsus grafik quyidagi rasmdagi kabi to'plamlarning holatini ko'rsatadi.

Yuqorida aytib o'tilgan strategiyadan foydalangan holda Kruskal algoritmini amalga oshirish uchun C dasturi quyidagicha:
#include
#include
#include
//vaznli chetni bildiruvchi struktura
struct Edge {
int manba, maqsad, vazn;
};
//vaznli, yo'naltirilmagan va bog'langan grafikni bildiruvchi tuzilma
strukturaviy grafik {
int Node, E;
struct Edge* chekkasi;
};
//V uchlari va E qirralari bilan grafikni saqlash uchun xotira ajratadi
struct Graph* GenerateGraph(int Node, int E)
{
struct Graph* grafigi = (struct Graph*)(malloc(sizeof(struct Graph)));
graph->Tugun = Tugun;
grafik->E = E;
graph->edge = (struct Edge*)malloc(sizeof(struct Edge));
qaytish grafigi;
}
// Union-Find uchun pastki to'plam
struct tree_maintainance_set {
int ota;
int darajasi;
};
//yo'lni siqish yordamida tanlangan i element to'plamini topadi
int find_DisjointSet(struct tree_maintainance_set subsets[], int i)
{
//ildizni toping va ildizni i ning ota-onasi sifatida qiling
agar (quyi to'plamlar[i].parent != i)
pastki to'plamlar[i].ota-ona
= find_DisjointSet(quyi to'plamlar, kichik to'plamlar[i].ota-ona);
pastki to'plamlarni qaytarish[i].ota-ona;
}
//Ikki to'plamdan birlashmani yaratadi
void Union_DisjointSet(struct tree_maintainance_set subsets[], int x, int y)
{
int xroot = find_DisjointSet(quyi to'plamlar, x);
int yroot = find_DisjointSet(quyi to'plamlar, y);
//eng past darajali daraxtni eng yuqori darajali daraxtga ulash
agar (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;
//agar darajalar bir xil bo'lsa, bitta tugunning darajasini o'zboshimchalik bilan oshiring
boshqa
{
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
//C dasturlashda qsort() yordamida qirralarni solishtirish funksiyasi
int myComp(const void* a, const void* b)
{
struct Edge* a1 = (struct Edge*)a;
struct Edge* b1 = (struct Edge*)b;
a1->og'irlik > b1->og'irlikni qaytarish;
}
//Kruskal yondashuvidan foydalanib MSTni qurish funksiyasi
Void KruskalMST(struct Graph* grafigi)
{
int Node = graph-> Tugun;
struct Edge
natija[tugun]; 
int e = 0; 
int i = 0; 
//barcha qirralarni saralash
qsort(grafik->qirra, grafik->E, sizeof(grafik->qirra[0]),
myComp);
//V kichik to'plamlar uchun xotira ajratish
struct tree_maintainance_set* kichik to'plamlari
= (struct tree_maintainance_set*)malloc(Node * sizeof(struct tree_maintainance_set));
//Faqat bitta elementni o'z ichiga olgan V kichik to'plamlar
uchun (int v = 0; v < tugun; ++ v) {
subsets[v].ota-ona = v;
subsets[v].rank = 0;
}
//Chetning o'tish chegarasi: V-1
while (e < Tugun - 1 && i < grafik->E) {
struct Edge next_edge = graph->chekka [i++];
int x = find_DisjointSet(quyi to'plamlar, next_edge.source);
int y = find_DisjointSet(quyi to'plamlar, keyingi_chekka.destination);
agar (x != y) {
natija[e++] = keyingi_chekka;
Union_DisjointSet(quyi to'plamlar, x, y);
}
}
// MSTni chop etish
printf(
"MSTda yaratilgan qirralar quyida keltirilgan: \n");
int minimalCost = 0;
uchun (i = 0; i < e; ++i)
{
printf("%d -- %d == %d\n", natija[i].manba,
natija[i].maqsad, natija[i].ogirlik);
minimalCost += natija[i].og'irlik;
}
printf("Yaratilgan MST narxi: %d", minimal narx);
qaytish;
}
int main()
{
int tugun = 4; 
int E = 6; 
struct Graph* graph = GenerateGraph(tugun, E);
//Qiymatni qo'lda kiritish bilan grafik yaratish
// chetiga 0-1 qo'shing
graph->edge[0].source = 0;
graph->edge[0].destination = 1;
graph->chet[0].weight = 2;
}
// chetiga 0-2 qo'shing
graph->chet[1].source = 0;
graph->chekka [1].destination = 2;
graph->chet[1].weight = 4;
// chetiga 0-3 qo'shing
graph->chet [2].source = 0;
graph->chekka [2].destination = 3;
graph->chet[2].weight = 4;
// chekka 1-3 qo'shing
graph->chet[3].source = 1;
graph->chekka [3].destination = 3;
graph->chet[3].weight = 3;
// chetiga 2-3 qo'shing
graph->chet[4].source = 2;
graph->chekka [4].destination = 3;
graph->chet[4].weight = 1;
// chekka 1-2 qo'shing
graph->chet[5].source = 1;
graph->chet[5].destination = 2;
graph->chet[5].weight = 2;
KruskalMST(grafik);
qaytish 0;
}