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,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(:,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',1)),'v',2)),')']);endaxis 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)*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),temp);endfor i=1:nE plot(x(1,e(i,:)),'b');endfor i=1:length(P(:,4)) plot(x(1,Pp(i,1:2)),'r','linewidth',3);endtext(-0.35,-1.2,['最小生成树的权为',num2str(Wt)]);Title('红色连线为最小生成树');axis off;hold off;main
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)结果
获取自:http://blog.sina.com.cn/s/blog_8041c9c90100xljz.html
总结以上是内存溢出为你收集整理的最小生成树全部内容,希望文章能够帮你解决最小生成树所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)