实际背景与算法

实际背景与算法

实际背景:

要在n个居民点之间架设煤气管道,很显然最多可架设 n(n-1)/2条管道,然而要

连通n个居民点架设n-1条管道(无环出现)就可以了,为了使造价最小,选择哪n-1条边?这就是最小生成树问题。

算法1（prim算法）：

1）图采用邻接矩阵存储。

2）找到目前情况下能连上的权值最小的边的另一端点，加入之，直到所有的顶点加入完毕。

算法2（kruskal算法）：

1）图采用边目录方式存储。

2）选目前情况下能连上的权值最小的边，若与以生成的树不够成环，加入之，直到n-1条边加入完毕。

1.2例题与习题

1：求下图的最小生成树

程序1（使用算法1）如下：

programmintree;
const maxn=100;
var cost:array[1..maxn,1..maxn] of integer;
    lowcost,closet:array[1..maxn] of integer;
    n,mincost:integer;
procedure init;
var i,j:integer;
begin
readln(n);
for i:=1 to n do
   for j:=1 to n do
    read(cost[i,j]);
for i:=1 to n do
   begin
   lowcost:=cost[1,i];
   closet:=1
   end ;
mincost:=0;
end;
procedure prim;
var i,j,k,min:integer;
begin
for i:=1 to n-1 do
  begin
  min:=32767;
  for j:=1 to n do
   if (lowcost[j]<>0) and (lowcost[j]<min) then
    begin
     min:=lowcost[j];k:=j;
    end;
  mincost:=mincost+cost[closet[k],k];
  writeln('(',closet[k],',',k,')');
  lowcost[k]:=0;
  for j:=1 to n do
   if cost[k,j]<lowcost[j] then
    begin lowcost[j]:=cost[k,j];closet[j]:=k end;
end;
end;
begin
init;
prim;
writeln('treeminlength=',mincost);
readln;
end.

程序2（使用算法2）如下：

programshchtree;
var n,m,i,j:integer;
selected:array[1..100] of integer;
e:array[1..100,1..2] of integer;
value:array[1..100] of integer;
t:array[1..100] of integer;
min,mine,valuet:integer;
begin
write('Input n and m:');read(n,m);
writeln('input data:');
for i:=1 to m do readln(e[i,1],e[i,2],value);
fillchar(selected,sizeof(selected),0);
fillchar(t,sizeof(t),0);
valuet:=0;
for i:=1 to n-1 do
  begin
   min:=maxint;
   mine:=0;
   for j:=1 to m do
    if selected[j]=0 then
     if ((t[e[j,1]]=0) xor (t[e[j,2]]=0)) or (i=1) then
      if value[j]<min then
       begin min:=value[j];mine:=j; end;
   selected[mine]:=1;
   t[e[mine,1]]:=1;
   t[e[mine,2]]:=1;
   valuet:=valuet+min;
  end;
   for i:=1 to m do
   if selected=1 then
    begin writeln('(',e[i,1],',',e[i,2],')'); end;
   writeln('tree:  ','length=',valuet);

readln;
end.