菜鸟求解
pascal吧
全部回复
仅看楼主
level 3
最小生成树 问题
2014年02月09日 03点02分 1
level 3
pascal中如何打表?
2014年02月09日 06点02分 2
level 3

const
<?xml:namespace prefix="o" ns="urn:schemas-microsoft-com:office:office"></?xml:namespace>
vmax=200;
var
w:array[1..vmax,1..vmax] of integer;
i,j,k,v,e:integer;
procedure prim(v0:integer);
var
flag:array[1..vmax] of boolean;
min,prevk,nextk:integer;
begin
fillchar(flag,sizeof(flag),false);
flag(v0):=true;
for i:=1 to v-1 do
begin
min:=maxint;
for k:=1 to v do
if flag[k] then
for j:=1 to v do
if(not(flag[j])) and(w[k,j]<min) and(w[k,j]<>0) then
begin
min:=w[k,j];
nextk:=j;
prevk:=k;
end;
if min<>maxint then
begin
flag[nextk]:=true;
writeln(prevk,' ',nextk,' ',min);
end;
end;
end;
begin
fillchar(w,sizeof(w),0);
readln(v,e);
for k:=1 to e do
begin
read(i,j);
readln(w[i,j]);
w[j,i]:=w[i,j];
end;
prim(1);
end.
有没有更好的方法?
2014年02月09日 08点02分 5
level 5
这貌似是Kruskal吧?
最小生成树两种算法,Prim和Kruskal,从实用性上来说没有更好的了。
2014年02月13日 04点02分 6
1