最小生成树matlab程序.doc

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));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,:);  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]=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');fori=1:n  temp=['v',int2str(i)];  text(x(1,i),y(1,i),temp);endfori=1:nE  plot(x(1,e(i,:))