Algoritmlarni loyihalash fani

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

Download 86,79 Kb.

bet	2/2
Sana	13.07.2022
Hajmi	86,79 Kb.
	#786018

1 2

Bog'liq
Algoritmlarni loyihalash fani

Краскал алгоритми .

Танланган тугунлар тўплами	(u,v) қирра	V/U танланмаган тугунлар тўплами
Изоҳ
	{ }		{A,B,C,D,E,F,G}	Бошланғич граф

Қуйида Прим алгоритми келтирилган.
1-дастур. Прим алгоритми
procedure Prim ( G: граф; var T: қирралар тўплами );
var
U: қирралар тўплами;
u, v: қирра;
begin
T:= ø;
U:= {1};
while U ≠ V do begin
энг кам нархли ва u U ва v V\U бўлган (u, v) қиррани топиш;
Т:= Т {u, V));
U:= U {v}
end
end; { Prim }

Краскал алгоритми.
Ушбу алгоритм 1956 йили Краскал томонидан ишлаб чикилган.
Фараз қиламиз, V = {1, 2, .... n} бўғимлар тўпламидан иборат ва Е қирралар тўпламида аниқланган с нарх функцияси билан берилган G=(V, Е) боғланган граф бўлсин. Крускал алгоритмида G граф учун минимал нархли дарахтлар склетини қуриш G графнинг фақат n та бўғимларидан ташкил топган ва қирралари бўлмаган Т=(V, ø) графдан бошланади. Шундай қилиб, ҳар бир бўғим боғланган (ўзи-ўзи билан) компонент ҳисобланади. Алгоритм бажарилиши вақтида боғланган компонентлар наборига эга бўламиз, аста-секин бирлаштириб дарахтлар склетини ташкиллаштирамиз.
Аста-секин ўсувчи боғланган компонентларни қуришда Е тўпламдан қирралар уларнинг нархи ўсиши тартибида навбатма-навбат текширилади. Агар навбатдаги қирра турли компонентлардаги иккита бўғимни бирлаштирса, у ҳолда бу қирра Т графга қўшилади. Агар бу қирра битта компонентнинг иккита бўғимини бирлаштирса, у ташлаб юборилади, чунки унинг боғланган компонентга қўшилиши цикл ҳосил бўлишига олиб келади. G графнинг барча бўғимлари битта компонентга тегишли бўлса, Т минимал нархли дарахтлар склетини қуриш бу граф учун тугайди.
Мисол

yechish

#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<Download 86,79 Kb.
Do'stlaringiz bilan baham:

1 2