pascal普里姆算法

Question

type edge=record
fr,en,we:integer;
end;
var g:array[1..100,1..100] of integer;
ed:array[1..100] of edge;
n,i,j,k,min,m,s,w:integer;
t:edge;
begin
assign(input,'creat.in');
assign(output,'creat.out');
reset(input);
rewrite(output);
readln(n);
for i:=1 to n do
begin
for j:=1 to n do
begin
read(g[i,j]);
if g[i,j]=0 then
g[i,j]:=maxint;
end;
readln;
end;
for i:=1 to n-1 do
begin
ed[i].fr:=1;
ed[i].en:=i+1;
ed[i].we:=g[i,i+1];
if ed[i].we=0 then
ed[i].we:=maxint;
end;
for k:=1 to n-1 do
begin
min:=maxint;
m:=k;
for j:=k to n-1 do
if (ed[j].we<min)and(ed[j].we<>0) then
begin
MIN:=ED[J].WE;
M:=J;
END;
if m<>k then
begin
t:=ed[k];
ed[k]:=ed[m];
ed[m]:=t;
end;
j:=ed[k].en;
for i:=k+1 to n-1 do
begin
s:=ed[i].en;
w:=g[j,s];
if w<ed[i].we then
begin
ed[i].we:=w;
ed[i].fr:=j;
end;
end;
end;
w:=0;
for i:=1 to n-1 do
begin
writeln('edge ',i,' fr: ',ed[i].fr,' en: ',ed[i].en,' we ',ed[i].we);
w:=w+ed[i].we;
end;
writeln(w);
close(input);
close(output);
end.

哪位高手把每一部都说一下意思，小弟感激不仅！！！

Answer 1

Prim算法用于求无向图的最小生成树
设图G =（V，E），其生成树的顶点集合为U。
①、把v0放入U。
②、在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。
③、把②找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行②。
其算法的时间复杂度为O(n^2)
Prim算法实现：
（1）集合：设置一个数组set(i=0,1,..,n-1),初始值为 0,代表对应顶点不在集合中（注意：顶点号与下标号差1）
（2）图用邻接阵表示，路径不通用无穷大表示，在计算机中可用一个大整数代替。
采用堆可以将复杂度降为O(m log n)，如果采用Fibonaci堆可以将复杂度降为O(n log n + m)

参考资料：http://baike.baidu.com/view/671819.html?wtp=tt

Answer 2

program prim; {理工P106 输出：各个顶点的指向 注意初始的距阵，无连接的边表示为0 后被赋值maxint}
const maxn=100; {无最小生成树的权值和无生成时取点顺序记录，只有指向}
var cost:array[1..maxn,1..maxn] of integer;
mincost,closed:array[1..maxn]of integer;
min,k,i,j,n,x,y:integer;
begin
assign( input,'prim1.in'); reset(input);
assign(output,'prim1.out');rewrite(output);
readln(n);
for i:=1 to n do begin
for j:=1 to n do begin
read(cost[i,j]);
if (i<>j) and (cost[i,j]=0) then cost[i,j]:=maxint;
end;
readln;
end;
for i:=1 to n do begin
mincost[i]:=cost[1,i]; closed[i]:=1;end;
for i:=2 to n do begin
min:=maxint;
for j:=1 to n do
if (mincost[j]<min) and (mincost[j]<>0) then begin
min:=mincost[j];
k:=j; end;
mincost[k]:=0;
for j:=1 to n do
if (mincost[j]>cost[k,j]) and (mincost[j]<>0) then begin
mincost[j]:=cost[k,j];
closed[j]:=k; end;
end;
for i:=2 to n do
writeln(i:4,'---->',closed[i]:4);
close(input); close(output);
end.
6
0 7 6 2 0 0
7 0 0 4 4 0
6 0 0 5 0 3
2 4 5 0 5 4
0 4 0 5 0 6
0 0 3 4 6 0
----------------------------------------------------------------------------------------------------------------------------------------------------------
5
0 2 12 10 0
2 0 8 0 9
12 8 0 6 3
10 0 6 0 7
0 9 3 7 0