图论中最小生成树Kruskal算法 及画图程序 M-函数
图论中最小生成树Kruskal算法 及画图程序 M-函数function =mintreek(n,W)
%图论中最小生成树Kruskal算法 及画图程序 M-函数
%格式 =mintreek(n,W)：n为图顶点数,W为图的带权邻接矩
% 阵，不构成边的两顶点之间的权用inf表示。显示最小生成树的边及
% 顶点, Wt为最小生成树的权,Pp(:,1:2)为最小生成树边的两顶点,
% Pp(:,3)为最小生成树的边权,Pp(:,4)为最小生成树边的序号;
%附图,红色连线为最小生成树的图;
%例如
% n=6;w=inf*ones(6);
% w(1,)=;w(2,)=;
% w(3,)=;w(4,6)=2;w(5,6)=6;
% =mintreek(n,w)
% By X.D. Ding June 2000
tmpa=find(W~=inf);=find(W~=inf);
w=W(tmpa);e=; %w是W中非inf元素按列构成的向量
%e的每一行元素表示一条边的两个顶点的序号
=sort(w);E=;=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));
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(:,1)-E(:,2));E=E(a,:);
if (rank(E)>0),P=;k=length(E(:,1)); end;
end;
Wt=sum(P(:,3));Pp=;
for i=1:length(P(:,3)); %显示顶点vi与边ej
disp([' ','e',num2str(P(i,4)),' ','(v',...
num2str(P(i,1)),' ','v',num2str(P(i,2)),')']);
end;
% 以下是画图程序
axis equal; hold on
=cylinder(1,n);xm=min(x(1,:)); ym=min(y(1,:));
xx=max(x(1,:)); yy=max(y(1,:));
axis(); plot(x(1,:),y(1,:),'ko')
for i=1:n; temp=[' v',int2str(i)];
text(x(1,i),y(1,i),temp); end;
for i=1:nE; plot(x(1,e(i,:)),y(1,e(i,:)),'b'); end;
for i=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');hold off
页:
[1]