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

时间:2022-10-05 06:48:08

Prim算法

数学建模(14)——MATLAB实现最小生成树(Prim与Kruskal算法)
连通赋权图如上
邻接矩阵如下
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