中财网行尸肉心第一季爱奇艺:图，最小生成树 MATLAB程序
来源：百度文库 编辑：中财网 时间：2024/04/29 19:27:30
function [b,u,w]=mintrees(a,k)%最小生成树 ，a 邻接矩阵，k 起点
if nargout==1
k=1;
end
[m,n]=size(a);
for i=1:m
for j=1:n
if a(i,j)==0
a(i,j)=inf;
end
end
end
b=zeros(n);
u(1)=k;
j=1;
v=zeros(1,n);
v(k)=1;
for o=1:n-1
sn=ones(3,n)*inf;
for xk=1:j
k=u(xk);
p=max(a(k,:));
for i=1:n
if v(i)<1&a(k,i)
end
end
for i=1:n
if v(i)<1&a(k,i)==p
break;
end
end
sn([1 2 3],k)=[i,p,u(xk)];
end
[w(j),k]=min(sn(2,:));
j=j+1;
u(j)=sn(1,k);
b(sn(1,k),sn(3,k))=sn(2,k);
v(u(j))=1;
end
如：输入邻接矩阵
0 2 5 4 0 0 0
2 0 2 0 0 7 0
5 2 0 1 3 5 0
4 0 1 0 4 0 0
0 0 3 4 0 1 7
0 7 5 0 1 0 5
0 0 0 0 7 5 0
a(1,[2 3 4])=[2 5 4];a(2,[1 3 6])=[2 2 7];
a(3,[1 2 6 5 4])=[5 2 5 3 1];
a(4,[1 3 5])=[4 1 4];
a(5,[4 3 6 7])=[4 3 1 7 ];
a(6,[2 3 5 7])=[7 5 1 5];
a(7,[6 5])=[5 7];
b=mintrees(a)
结果：
b =
0 0 0 0 0 0 0
2 0 0 0 0 0 0
0 2 0 0 0 0 0
0 0 1 0 0 0 0
0 0 3 0 0 0 0
0 0 0 0 1 0 0
0 0 0 0 0 5 0
b为最小生成树的邻接矩阵
0