Inainte de a raspunde la intrebare, sa consideram, de exemplu, graful din Figura 6.1.a. Ordonam crescator (in functie de cost) muchiile grafului: {1, 2}, {2, 3}, {4, 5}, {6, 7}, {1, 4}, {2, 5}, {4, 7}, {3, 5}, {2, 4}, {3, 6}, {5, 7}, {5, 6} si apoi aplicam algoritmul. Structura componentelor conexe este ilustrata, pentru fiecare pas, in Tabelul 1.
Figura 1 Un graf si arborele sau partial de cost minim.
Tabelul 1 Algoritmul lui Kruskal aplicat grafului din Figura1a.
Multimea A este initial vida si se completeaza pe parcurs cu muchii acceptate (care nu formeaza un ciclu cu muchiile deja existente in A). In final, multimea A va contine muchiile {1, 2}, {2, 3}, {4, 5}, {6, 7}, {1, 4}, {4, 7}. La fiecare pas, graful partial
In vectorul V vom sorta in ordine crescatoare numarul muchiilor in ordine crescatoare in functie de costul fiecareia.In vectorul X vom retine pentru fiecare nod numarul componenetei din care face parte acesta si care se schimba o data ce adaugam o noua muchie.Modificarea acestuia se face in functie de apartenenta uneia dintre extremitati la un arbore cu mai mult de un nod.In multimea B se retin numerele de ordine ale muchiilor ce apartin arborelui de cost minim.
procedure sortare; {se face sortarea intr-un vector v a muchiilor in ordine
var i,k,min:integer; crescatoare a costurilor muchiilor}
c:vector;
begin
c:=a;k:=0;
repeat
min:=maxint;
for i:=1 to m do
if (c[i].cost
begin
min:=c[i].cost;
j:=i;
end;
inc(k);
v[k]:=j;
c[j].cost:=0;
until k=m;
end;
procedure kruskal;
var i,k,j:integer;
begin
k:=0;
for i:=1 to m do
begin
if (x[a[v[i]].vf1]=0) and (x[a[v[i]].vf2]=0) then {ambele extremitati
begin formeaza un arbore cu un singur nod}
b:=b+[v[i]];
inc(k);
x[a[v[i]].vf1]:=k;
x[a[v[i]].vf2]:=k;
end
else
if x[a[v[i]].vf1]<>x[a[v[i]].vf2] then {se verifica daca extremitatile
begin muchiei sunt din arbori diferiti}
b:=b+[v[i]];
if (x[a[v[i]].vf1]<>0) and (x[a[v[i]].vf2]<>0) then
begin
for j:=1 to n do
if (x[j]=x[a[v[i]].vf1]) and (a[v[i]].vf1<>j) then
x[j]:=x[a[v[i]].vf2];
x[a[v[i]].vf1]:=x[a[v[i]].vf2];
end;
if (x[a[v[i]].vf1]=0) then
x[a[v[i]].vf1]:=x[a[v[i]].vf2];
if (x[a[v[i]].vf2]=0) then
x[a[v[i]].vf2]:=x[a[v[i]].vf1];
end;
suma:=suma+a[v[i]].cost;
end;
end;
begin {main}
clrscr;
citire;
for i:=1 to m do
v[i]:=0;
sortare;
writeln('Vectorul sortat in ordinea muchiilor este:');
for i:=1 to m do
write(v[i],' ');
writeln;
for i:=1 to n do
x[i]:=0;
b:=[];
kruskal;
writeln('Muchiile arborelui sunt:');
suma:=0;
for i:=1 to m do
if i in b then
begin
writeln('Muchia ',i,':',a[i].vf1,' ',a[i].vf2,' de cost ',a[i].cost);
suma:=suma+a[i].cost;
end;
write('Costul arborelui este:',suma);
readkey;
end.
Niciun comentariu:
Trimiteți un comentariu