最小生成树的Kruskal算法.docx

《最小生成树的Kruskal算法.docx》由会员分享，可在线阅读，更多相关《最小生成树的Kruskal算法.docx（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、最小生成树的Kruskal算法1.2Kruskal算法与Dijkstra算法的MATLAB程序1.Kruskal算法的MATLAB程序FunctionWt,Pp=mintreek(n,W)%图论中最小生成树Kruskal算法及画图程序M函数%格式Wt,Pp=mintreek(n,W)：n为图顶点书，W为图的带权邻接矩阵，不构成边的两点之间的权用Inf表示。显示最小生成树的边及顶点，Wt为最小生成树的权，Pp(:,1:2)为最小生成树边的辆顶点，Pp(:,3)为最小生成树的边权%Pp(:,4)为最小生成树边的序号%附图，红色连线为最小生成树的图Tmpa=find(W=inf);tmpb,tmpc

2、=find(w=inf);%w是W中非inf元素按列构成的向量w=W(tmpa);e=tmpb,tmpc;%e的每一行元素表示一条边的两个顶点的序号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,2),E(1,1);fori=1:k;if(E(i,1)=temp1),E(i,1)=temp2;end;if(E(i,2)=temp1

3、),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);end;End;Wt=sum(P(:,3);Pp=e(P(:,4),:),P(:,3:4);%显示顶点vi与边ejFori=1:length(P(:,3);Disp(,e,num2str(P(i,4),(v,Num2str(P(i,1),v,num2str(P(i,2),);end;%下面是画图程序axisequal;holdonx,y=cylinder(n,1);xm=min(x(1,:);ym=min(y(

4、1,:);xx=max(x(1,:);yy=max(y(1,:);axis(xm-abs(xm)*0.15,xx+abs(ym)*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);end;fori=1:nE;plot(x(1,e(i,:),y(1,e(i,:),b);endfori8=1:length(P(:,4);plot(x(1,Pp(i,1:2),y(1,Pp(i,1:2),r);end;text(-0.35,-1.2,最小生成树的权为，,num2str(Wt);title(红色连线为最小生成树);axis(off);holdoff