资源描述：
《最小生成树matlab程序.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
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
2、));E=E(temp,:);P=E(1,:);k=length(E(:,1));whilerank(E)>0 temp1=max(E(1,2),E(1,1)); temp2=min(E(1,2),E(1,1)); fori=1:k ifE(i,1)==temp1 E(i,1)=temp2; end ifE(i,2)==temp1 E(i,2)=temp2; end end a=find(E(:,1)-E(:,2)); E=E(a,:);
3、ifrank(E)>0 P=[P;E(1,:)]; k=length(E(:,1)); endendWt=sum(P(:,3));Pp=[e(P(:,4),:),P(:,3:4)];fori=1:length(P(:,3)) disp(['','e',num2str(P(i,4)),'',... '(v',num2str(P(i,1)),'','v',num2str(P(i,2)),')']);endaxisequal;%画最小生成树 holdon[x,y]=cylinde
4、r(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');fori=1:n temp=['v',int2str(i)]; text(x(1,i),y(1,i),temp);endfori=1:nE plot(x(1,e(i,:
5、)),y(1,e(i,:)),'b');endfori=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('红色连线为最小生成树');axisoff;holdoff;调用此程序要先编写主程序。例：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
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
