O`ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI
UNIVERSITETI SAMARQAND FILIALI
"Telekominikatsion injiniring" fakulteti
" ALGORITMLARNI LOYIHALASH " fanidan
Guruh: 205
Bajardi: Berdiqulov Bexruz
Qabul qildi: Iskandarova Feruza
Samarqand – 2020
Quyidagi nazariy savollarga javob bering
Prim algoritmi ni tushuntirib bering
Ушбу алгоритм Роберт Прим томонидан 1957 йили ишлаб чиқилган. Унгача 1930 йили чех математиги Войтек Ярник (Vojtěch Jarník) томонидан, кеийнроқ 1959 йилда Эдгар Дейкстра (Edsger Dijkstra) томонидан ишлаб чикилган.
Минимал нархли дарахтлар склетини қуришнинг иккита кенг тарқалган усули мавжуд. Улардан бири Прим алгоритми. Бу алгоритмда дарахтлар склети «ўсадиган» ("вырастает") U қирралар тўплами қурилади. V={1, 2,..., n} бўлсин. Аввал U={1} бўлади. Алгоритмнинг ҳар бир қадамида минимал нархли қирра топилади, ундан кейин v қирра V\U тўпламдан U тўпламга ўтказилади. Бу жараён U тўплам V тўпламга тенг бўлгунча такрорланади.
Misol:
Мисол
|
Танланган тугунлар тўплами
|
(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 бўлди.
|
Қуйида Прим алгоритми келтирилган.
1-дастур. Прим алгоритми
procedure Prim ( G: граф; var T: қирралар тўплами );
var
U: қирралар тўплами;
u, v: қирра;
begin
T:= ø;
U:= {1};
while U ≠ V do begin
энг кам нархли ва uU ва vV\U бўлган (u, v) қиррани топиш;
Т:= Т{u, V));
U:= U{v}
end
end; { Prim }
Юқоридаги граф учун қўшнилик матрицаси
A B C D E F G
0 7 0 5 0 0 0
7 0 8 9 7 0 0
0 8 0 0 5 0 0
5 9 0 0 15 6 0
0 7 5 15 0 8 9
0 0 0 6 8 0 11
0 0 0 0 9 11 0
Дастур
#include
using namespace std;
int main()
{
int a,b,u,v,n,i,j,ne=1;
int visited[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;i
for(j=0;j
{
cin>>cost[i][j];
if(cost[i][j]==0)
cost[i][j]=999; // 999 - это что-типа бесконечности. Должно быть больше чем значения веса каждого из ребер в графе
}
visited[0]=1;
cout<<"\n";
while(ne < n)
{
for(i=0, min=999; i
for(j=0;j
if(cost[i][j]< min)
if(visited[i]!=0)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
if(visited[u]==0 || visited[v]==0)
{
path[path_index]=b;
path_index++;
ne++;
mincost+=min;
visited[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 "<
return 0;
}
Do'stlaringiz bilan baham: |