《最小生成树matlab程序(4页).doc》由会员分享，可在线阅读，更多相关《最小生成树matlab程序(4页).doc（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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(E)0 temp1=m
2、ax(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); endendWt=sum(P(:,3);Pp=e(P(:,4),:),P(:,3:4);for i=1:length(P(:,3) disp(,e,num2str(P(i,4),. (v,num2str(
3、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(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
4、(i,:),y(1,e(i,:),b);endfor i=1:length(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在窗口中运行此程序得：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 4 8 2 3 5 3-第 4 页-