最小生成树matlab程序(共4页).docx

精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
function [Wt,Pp]=mint精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
function [Wt,Pp]=mintree(n,W)
%求最小生成树，n为顶点个数，W是权值邻接矩阵，不相邻的用inf表示
%Wt是最小生成树的权，Pp（：，1：2）表示最小生成树的两顶点
%Pp(:，4)表示最小生成树的序号
tmpa=find(W~=inf);
[tmpb,tmpc]=find(W~=inf);
w=W(tmpa);
e=[tmpb,tmpc];
[wa,wb]=sort(w);
E=[e(wb,:),wa,wb];
[nE,mE]=size(E);
temp=find(E(:,1)-E(:,2));
E=E(temp,:);
P=E(1,:);
k=length(E(:,1));
while rank(E)>0
    temp1=max(E(1,2),E(1,1));
    temp2=min(E(1,2),E(1,1));
    for i=1:k
        if E(i,1)==temp1
            E(i,1)=temp2;
        end
        if E(i,2)==temp1
            E(i,2)=temp2;
        end
    end
    a=find(E(:,1)-E(:,2));
    E=E(a,:);
    if rank(E)>0
        P=[P;E(1,:)];
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
        k=length(E(:,1));
    end
end
Wt=sum(P(:,3));
Pp=[e(P(:,4),:),P(:,3:4)];
for i=1:length(P(:,3))
    disp(['','e',num2str(P(i,4)),'',...
        '(v',num2str(P(i,1)),'','v',num2str(P(i,2)),')']);
end
axis equal;%画最小生成树   
hold on
[x,y]=cylinder(1,n);
xm=min(x(1,:));
ym=min(y(1,:));
xx=max(x(1,:));
yy=max(y(1,:));
axis([xm-abs(xm)*,xx+abs(xx)*,ym-abs(ym)*,yy+abs(yy)*]);
plot(x(1,:),y(1,:),'ko');
f