Program Thuat_toan_Prim;
Uses crt;
Var
kt : array[1..50] of boolean;
trongso : array[1..50,1..50] of integer;
dinh : array[1..50] of integer;
dinhke : array[1..50] of integer;
n,m,t: integer;
i,j: integer;
ch: char;
f:text;
Procedure Inmatran;
Begin
(*In ma tran ra *)
Writeln('-------------------------------------------------------');
For i:=1 to n do
Begin
For j:=1 to n do
If TrongSo[i,j]=Maxint then write(' 0',' ')
Else write(TrongSo[i,j]:4,' ');
Writeln;
End;
Writeln('-------------------------------------------------------');
End;
Procedure Nhap;
Var
z: integer;
Begin
assign(f,'dothi6.inp');
reset(f);
readln(f,n,m);
For z:=1 to m do
begin
readln(f,i,j,trongSo[i,j]);
trongso[j,i]:=trongso[i,j];
end;
for i:=1 to n do
for j:=1 to n do
if trongso[i,j]=0 then trongso[i,j]:=maxint;
close(f);
end;
Procedure Prim;
Var
v,k,z,q,h: integer;
min: integer;
Begin
Write('Chon dinh bat dau thuat toan: ');readln(z);
dinh[1]:=z; kt[z]:=true;
q:=1;
repeat
min:=maxint;
for z:=1 to q do
begin
for i:=1 to n do
begin
if (dinh[z]<>0) and (trongso[dinh[z],i]<=min) and not kt[i] then
begin
min:=trongso[dinh[z],i];
h:=dinh[z];
k:=i;
end;
if (dinhke[z]<>0) and (trongso[dinhke[z],i]<=min) and not kt[i] then
begin
min:=trongso[dinhke[z],i];
h:=dinhke[z];
k:=i;
end;
end;
end;
t:=t+min;
kt[k]:=true;
dinh[q]:=h;
dinhke[q]:=k;
inc(q);
until q=n;
end;
Procedure Intep;
Begin
Assign(f,'dothi6.out');
Rewrite(f);
Writeln(f,'-------------------------------------------------------');
For i:=1 to n do
Begin
For j:=1 to n do
If TrongSo[i,j]=maxint then write(f,' 0',' ')
Else write(f,TrongSo[i,j]:4,' ');
Writeln(f);
End;
Writeln(f,'-------------------------------------------------------');
writeln(f,'Cay khung nho nhat gom cac canh:');
For i:=1 to n-1 do
begin
write(f,'(',dinh[i],',',DinhKe[i],') ');
end;
writeln(f);
writeln(f,'Length: ',T);
close(f);
end;
Begin
clrscr;
writeln('THUAT TOAN PRIM TIM CAY KHUNG NHO NHAT');
writeln(' DUNG MA TRAN KE');
writeln('---------------------------------------');
Nhap;
Inmatran;
Prim;
Intep;
write('Cac canh cua cay khung be nhat:');
for i:=1 to n-1 do write('(',dinh[i],',',DinhKe[i],')');
writeln;
writeln('Do dai cua cay khung : ',t);
writeln('***************************************');
writeln('Nhan phim Enter de tiep tuc.');
readln;
end.
