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

Download 13,47 Kb.
bet	2/2
Sana	20.12.2023
Hajmi	13,47 Kb.
	#124402

1 2

Bog'liq
2. Laboratoriya mashg’uloti Mavzu Kruskal algoritmi. Prima algo-hozir.org

Mustaqil yechish uchun masalalar

Танланган тугунлар тўплами

(u,v) қирра

V/U
танланмаган тугунлар тўплами

Изоҳ

{ }
{A,B,C,D,E,F,G}

Бошланғич граф

{D}

(D,A)=5 V
(D,B) = 9
(D,E)= 15
(D,F) = 6

{A,B,C,E,F,G}

D тугундан бошлаймиз A, B, E и F лар D билан боқланган. A тугун — D га энг яқин бўлганлиги учун шу тугун олинади.

{A,D}

(D,B) = 9
(D,E)= 15
(D,F) = 6
(A,B) = 7 V

{B,C,E,F,G}

D ёки A га энг яқин бўлган тугунни топамиз. B - D 9, A —D 7. E гача масофа 15, F —гача 6. F энг яқин тугун.

{A,B,D,F}

(B,C) = 8
(B,E)=7 V
(D,B) = 9 цикл
(D,E)= 15
(F,E) = 8
(F,G)= 11

{C,E,G}

{A,B,D,E,F}

(B,C) = 8

(D,B) = 9 цикл
(D,E) = 15 цикл
(E,C) = 5 V
(E,G) = 9
(F,E) = 8 цикл
(F,G) = 11

{C,G}

{A,B,C,D,E,F}

(B,C) = 8 цикл

(D,B) = 9 цикл
(D,E) = 15 цикл
(E,G) = 9 V
(F,E) = 8 цикл
(F,G) = 11

{G}

{A,B,C,D,E,F,G}

(B,C) = 8 цикл

(D,B) = 9 цикл
(D,E) = 15 цикл
(F,E) = 8 цикл
(F,G) = 11 цикл

{ }

Минимал нархли дарахтлар склети қурилди. Бунда оғирлиги 39 бўлди.
Masalaning dasturi:

#include

using namespace std;
int main()
{int a,b,u,v,n,i,j,ne=1;
int mas[10]={0}, min, mincost=0,cost[10][10];
int path[100]={0}; //ushbu massivda yulni tashkil qiladigan tugunlar yoziladi
int path_index=0;
cout<<"Tugunlar sonini kiriting "; cin>>n;
cout<<"Qushnilik matritsasini kiriting\n";
for(i=0;ifor(j=0;j{cin>>cost[i][j];
if(cost[i][j]==0)
cost[i][j]=999;
}mas[0]=1;
cout<<"\n";
while(ne < n)
{for(i=0, min=999; ifor(j=0;jif(cost[i][j]< min)
if(mas[i]!=0)
{min=cost[i][j];
a=u=i;
b=v=j;}
if(mas[u]==0 || mas[v]==0)
{path[path_index]=b;
path_index++;
ne++;
mincost+=min;
mas[b]=1;}
cost[a][b]=cost[b][a]=999; }
cout<<"\n";
cout<<1<<" --> ";
for (int i=0;i{ cout<
if (i "; }
cout<<"\n Minimal narx "}
3-masala: Jamshid – internet magazine ochgan. Turkiya tovarlarini sotish bo’yicha agent, unga 5 ta shahardan buyurtmalar tushdi. U yo’l harajatlarini tejamoqchi. Jamshid unga buyurtmalar tushgan har ikki shahar orasida yo’l harajatini hisoblab chiqqan. Masala yo’l harajatlarini kamaytirishdan iborat.
Dastlabki ma’lumotlar Jamshid Tovar tarqatishi kerak bo’lgan shaharlar ruyhati va yo’l harajatlari matrisasi ko’rinishida berilgan. Bu yerda matrisa i shahardan j shaharga borish narxiga teng bo’lgan c(i,j) elementlardan tashkil topgan ikki o’lchamli massiv. Shaharlar soni 20 ta bo’lsa, matrisa - bo’ladi.

P₁

P₂

P₃

P₄

P₅

P₁

P₂

P₃

P₄

P₅

Masala dasturi:

#include

using namespace std;
int main()
{ int cost, u,w, kk=100000, v,t, c[100][100],n;
cout<<"matritsa o'lchamini kiriting ">n;
cout<<"c[i][j] ">c[i][j];
t=0; cost=0; v=0;
cout<<"1 ->";
for(int k=0; k{ for(int i=0; iif(c[v][i]cout<";
cost+=c[v][t];
for(int i=0; ic[i][t]=0;
if(k!=(n-2)) c[t][0]=0;
v=t;
kk=10000000;
}
cout<<"1"return 0;}
Mustaqil yechish uchun masalalar

Pitsa tarqatuvchi ishchiga shaharning 6 ta nuqtasidan buyurtma tushdi. Pitsa tarqatuvchi hodimga shu buyurtma berilgan nuqtalar orasidagi masofalar ma’lum. U iqtisodiy tomondan va vaqt bo’yicha yutishga harakat qilmoqchi. Unga eng kam masofa bosib o’tgan holda pitsalarni tarqatib chiqishiga yordam bering.