最小生成树

概述mintree函数 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];[w mintree函数

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

总结

以上是内存溢出为你收集整理的最小生成树全部内容，希望文章能够帮你解决最小生成树所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。