最小生成树matlab程序

1、精选优质文档-倾情为你奉上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

2、(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     

3、      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);    endendWt=sum(P(:,3);Pp=e(P(:,4),:)

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),')');endaxis equal;%画最小生成树   hold onx,y=cylinder(1,n);xm=min(x(1,:);ym=min(y(1,:);xx=max

5、(x(1,:);yy=max(y(1,:);axis(xm-abs(xm)*0.15,xx+abs(xx)*0.15,ym-abs(ym)*0.15,yy+abs(yy)*0.15);plot(x(1,:),y(1,:),'ko');for i=1:n    temp='v',int2str(i);    text(x(1,i),y(1,i),temp);endfor i=1:nE    plot(x(1,e(i,:),y(1,e(i,:),'b');endfor i=1:length(

6、P(:,4)    plot(x(1,Pp(i,1:2),y(1,Pp(i,1:2),'r');endtext(-0.35,-1.2,'最小生成树的权为','',num2str(Wt);title('红色连线为最小生成树');axis off;hold off;调用此程序要先编写主程序。例：n=6;W=inf*ones(6);W(1,2,3,4)=6,1,5;W(2,3,5)=5,3;W(3,4,5,6)=5,6,4;W(4,6)=2;W(5,6)=6;a,b=mintree(n,W)命名为example在窗口

7、中运行此程序得：e2(v1v3)e9(v4v6)e6(v2v5)e8(v1v4)e3(v2v1)a =    15b =     1     3     1     2     4     6     2     9     2     5     3     6     3     6