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

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13

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