数学建模（14）——MATLAB实现最小生成树（Prim与Kruskal算法）

Prim算法

连通赋权图如上
邻接矩阵如下
0 50 60 0 0 0 0
0 0 0 65 40 0 0
0 0 0 52 0 0 45
0 0 0 0 50 30 42
0 0 0 0 0 70 0

function [result]=prim(a);
% 输入：a—邻接矩阵，a（i，j)是指i到j之间的权值
% 输出：result—第一、二、三行分别代表最小生成树边的起点、终点、权集合
a(a==0)=inf;
result=[];p=1;tb=2:length(a);
while size(result,2)~=length(a)-1
   temp=a(p,tb);temp=temp(:);
   d=min(temp);
[jb,kb]=find(a(p,tb)==d);
j=p(jb(1));k=tb(kb(1));
   result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];
end
end

Kruskal算法

function [result]=kruskal(a)
% 输入：a—邻接矩阵，a（i，j)是指i到j之间的权值
% 输出：result—第一、二、三行分别代表最小生成树边的起点、终点、权集合
[i,j,b]=find(a);
data=[i';j';b'];index=data(1:2,:);
loop=length(a)-1;
result=[];
while length(result)<loop
   temp=min(data(3,:));
   flag=find(data(3,:)==temp);
   flag=flag(1);
   v1=index(1,flag);v2=index(2,flag);
if v1~=v2
      result=[result,data(:,flag)];
   end
   index(find(index==v2))=v1;
data(:,flag)=[];
   index(:,flag)=[];
end
end