数学建模社区-数学中国

标题: 最小生成树——Prime算法 [打印本页]

作者: lovehaboy 时间: 2009-1-31 18:52
使用说明：
Dandn文件给出了输入参数的名称及格式
即在调用prim前先输入邻接矩阵D和节点个数n
输入prim
得到两行的矩阵T,将上下两行数字对应的节点相连即可

Dandn.m
D=[inf 7 8 2 inf inf 3 inf;
7 inf 1 inf 2 inf inf 3;
8 1 inf 4 2 7 inf inf;
2 inf 4 inf inf 4 6 inf;
inf 2 2 inf inf 5 inf 1;
inf inf 7 4 5 inf 4 3;
3 inf inf 6 inf 4 inf 6;
inf 3 inf inf 1 3 6 inf];
n=8;

Prime.m
T=[];l=0;%记录T的列数
q(1)=-1;
for i=2:n
p(i)=1;q(i)=D(i,1);
end
k=1;
while 1
if k>=n
      disp(T);
      break;
else
      min=inf;
      for i=2:n
         if q(i)>0&q(i)<min
            min=q(i);
            h=i;
         end
      end
end
l=l+1;
T(1,l)=h;T(2,l)=p(h);
q(h)=-1;
for j=2:n
      if D(h,j)<q(j)
         q(j)=D(h,j);
         p(j)=h;
      end
end
k=k+1;
end

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)