头衔：ENDLESS
等级：版主
文章：36
积分：116
注册：2004-11-24 |
 最小生成树
最小生成树
假设要在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。
在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。n个城市之间，最多可能设置n(n-1)/2条线路，那么，如何在这些可能的线路中选择n-1条，以使总的耗费最少呢？
普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法是两个利用MST性质构造最小生成树的算法。
123456①②③④⑤⑥⑤6556program prim;
const max=6;
of byte=((0,6,1,5,0,0),
(6,0,5,0,3,0),
(1,5,0,5,6,4),
(5,0,5,0,0,2),
(0,3,6,0,0,6),
(0,0,4,2,6,0));
of byte=(100,100,100,100,100); 扩展用数组，ss=0表示I点已扩展，ss<>0表示ss是当前所有已扩展点到点I的路径中的最短路径。
<>0表示I点与j点连
of byte; 存ss的另一端点，即s[I,p]=ss
i,j,l,m,n:integer;
begin
:=0; 清零
<>0 then begin ss:=s[1,i];p:=1 end;
ss数组赋初值，并找出与1点相通的所有点。
for i:=2 to max do
begin
l:=100;
for j:=2 to max do 找出与当前树中所有点相连的最短边中的最小边
end
建树
则替换
) then
:=n end;
end;
for i:=1 to max do 输出最小生成树矩阵
);writeln end;
writeln
end. |
|
|
|
注册
趣题之家 → 信息学竞赛 → 算法艺术 → 最小生成树
2005-03-15 23:09
