2. Laboratoriya mashg’uloti Mavzu: Kruskal algoritmi. Prima algoritmi. Xoffman daraxtlari Ishning maqsadi

12.1 Laboratoriya mashg’uloti
Mavzu: Kruskal algoritmi. Prima algoritmi. Xoffman daraxtlari
Ishning maqsadi: Kruskal va Prima algoritmlari asosida masalalar yechish
Kerakli jihozlar: Kompyuter, proyektor, doska, C++ dasturlash tili
Faraz qilamiz, V = {1, 2, .... n} bo’g’imlar to’plamidan iborat va Е qirralar to’plamida aniqlangan с narx funksiyasi bilan berilgan G=(V, Е) bog’langan graf bo’lsin. Krustal algoritmida G graf uchun minimal narxli darsxtlar skletini qurish G grafning faqat n ta bo’g’imlaridan tashkil topgan va qirralari bo’lmagan Т=(V, ø) grafdan boshlanadi. Shunday qilib, har bir bo’g’im bog’langan (o’z-o’zi bilan) component 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 Е 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 Т 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.
1-masala: Graf berilgan uni Kraskal metodi yordamida ishlab chiqing.

С bog’langan komponentlar to’plami kerak, bu uchun quyidagi operatorlar ishlatiladi:

1. MERGE(A, В, С) operatori С nabordan А va В bog’langan komponentlarni birlashtiradi va natijani А yoki В ga joylashtiradi.
2. FIND(B, С) funksiyasi С nabordan B bo’g’imni o’z ichiga olgan komponentning nomini qaytaradi.
3. INITIAL(A, B, С) operatori naborda faqat B bo’g’imdan iborat A nomli komponentni yaratadi.
Grafni kraskal metodi yordamida qurish dasturi:
#include
using namespace std;
int parent[9];
int find(int);
int uni(int,int);
int main()
{int min;
int i,j,k,a,b,u,v,n,ne=1;
int mincost=0,cost[9][9];
cout<<"\n\tImplementation of Kruskal's Algorithm\n";
cout<<"\nEnter the no. of vertices:";
cin>>n;
cout<<"\nEnter the cost adjacency matrix:\n";
for(i=1;i<=n;i++)
{ for(j=1;j<=n;j++)
{ cin>>cost[i][j];
if(cost[i][j]==0)
cost[i][j]=999; } }
cout<<"The edges of Minimum Cost Spanning Tree are\n";
while(ne < n)
{ for(i=1,min=999;i<=n;i++)
{ for(j=1;j <= n;j++)
{ if(cost[i][j] < min)
{ min=cost[i][j];
a=u=i;
b=v=j; } } }
u=find(u);
v=find(v);
if(uni(u,v))
{ cout<return i; }
int uni(int i,int j)
{ if(i!=j)
{ parent[j]=i;
return 1; }
return 0; }
Ushbu algoritm O (M log N + N²) vaqtda bajariladi. Qirralarni saralash uchun О(M logN) ta operatsiya kerak bo’ladi. Tugun u yoki bu qism daraxtga tegishli bo’lsa, tree_id massiv yordamida saqlanadi, bu massivda har bir tugun uchun u tegishli bo’lgan daraxt nomeri saqlanadi. Har bir qirra uchun О(1) vaqtda uning tugunlari turli daraxtlarga tegishli ekanli aniqlanadi. Nihoyat, ikkita daraxtni birlashtirish O (N) vaqtda bajariladi. Birlashtirish operatori O(N) o’tishda bajarilishini hisobga olsak, O (M log N + N²) kelib chiqadi.