最小生成树 matlab的图形显示 - 数学建模社区-数学中国

function [Wt,Pp]=mintree(n,W)8 {- W& \5 v& n6 |8 g) f/ V* I( d
%求最小生成树，n为顶点个数，W是权值邻接矩阵，不相邻的用inf表示
# K T' @2 @8 E1 b3 M+ ?* f
%Wt是最小生成树的权，Pp（：，1：2）表示最小生成树的两顶点
' J- G- B/ H/ |8 x
%Pp(:，4)表示最小生成树的序号
~: J) r% B2 z8 X" r2 ]- y5 Q
tmpa=find(W~=inf);
9 i! c% \7 A% _8 G7 n* ]
[tmpb,tmpc]=find(W~=inf);, M+ M" O5 d$ {+ O _! t8 l6 x
w=W(tmpa);
6 ~0 e- j! j4 l, h! c% d1 T2 e5 \
e=[tmpb,tmpc];
$ N3 e# | A) b# a: V
[wa,wb]=sort(w);! X$ U- H+ h& J5 L. X3 h
E=[e(wb,:),wa,wb];
* D. z% B% H& D0 k! o! R" C) q+ ^& O
[nE,mE]=size(E);
+ p9 I' l/ j# G0 u& |& k. t
temp=find(E(:,1)-E(:,2));) T0 L/ c8 L- R0 a
E=E(temp,:);
' H* u4 p7 n0 v, z/ k1 C! l W
P=E(1,:);
, R, ~3 S- A+ J3 x& b2 m
k=length(E(:,1));
$ _5 {* K% k1 T+ e6 }
while rank(E)>0% ~2 ?2 ?" U: q2 q
temp1=max(E(1,2),E(1,1));
* B0 C5 N/ J3 F7 f* k) h. m, i& D8 d
temp2=min(E(1,2),E(1,1));
3 H' c3 j" |0 e1 @9 L$ t. p
for i=1:k) M+ A% r2 a9 X# D! D9 f7 |1 U
if E(i,1)==temp1
' E" C* k% d& I' s; A7 Q6 S6 |
E(i,1)=temp2;
9 W" {: U6 W6 N+ T( A; K. |
end& F) H; ]9 O9 i' s
if E(i,2)==temp16 S6 I; l% C3 O; Z, M l2 O
E(i,2)=temp2;
! h! D6 f% A( ~
end2 N6 }4 @) a0 c& G" x7 c) K! `9 g/ G
end
: k/ d7 s, M8 F" j' p" ^
a=find(E(:,1)-E(:,2));0 F8 A$ g" I. m, H7 X6 k: T
E=E(a,:);
5 d9 s) |/ G3 X" |
if rank(E)>0
3 j" s$ i* y, v0 M7 I
P=[P;E(1,:)];
& D7 B4 e V* a' G2 r
k=length(E(:,1));! r0 X- e1 D" n0 s! R
end
3 f# G. L [, N; u
end& T" ]' h# |* q" u' Z
Wt=sum(P(:,3))
! `" W6 W7 |' V3 x
Pp=[e(P(:,4),:),P(:,3:4)];* ^) e4 T8 }8 ~0 y q. n
for i=1:length(P(:,3))8 H: e' z$ D' @$ Q, R
disp(['','e',num2str(P(i,4)),'',...
( H! s u5 h% P+ `0 o
'(v',num2str(P(i,1)),'','v',num2str(P(i,2)),')']);
% F6 t9 b* {. h4 X; P& p* \
end
' Y' V9 _. k0 ]
axis equal;%画最小生成树 h9 b3 _! d$ S* l- D# Y8 m
hold on
6 V) m0 Y. O3 X& o8 M V
[x,y]=cylinder(1,n);2 X0 D- {. b' ~6 O3 u( c; S, H
xm=min(x(1,:));- x Y) V, ~, X1 r
ym=min(y(1,:));
! M) I, e! I- m3 `; Q7 D( P
xx=max(x(1,:));
/ v0 J# H% C3 W: t( R9 R8 |, }
yy=max(y(1,:));# ^( j7 T% C1 j7 {1 A1 n0 f. F8 M
axis([xm-abs(xm)*0.15,xx+abs(xx)*0.15,ym-abs(ym)*0.15,yy+abs(yy)*0.15]);
+ m! Z6 W/ k2 y
plot(x(1,:),y(1,:),'ko');
/ o! t" v: n+ A9 {; \0 O
for i=1:n
; T9 l4 h4 u$ l1 E
temp=['v',int2str(i)];, u5 y: V4 J) E3 J1 L
text(x(1,i),y(1,i),temp);3 ?! \6 s! p: |2 g# {- [" J' S
end2 a; [- \7 x4 e* R q
for i=1:nE6 ~/ Y: T! `& V D) H: w
plot(x(1,e(i,:)),y(1,e(i,:)),'b');1 s6 n0 W* o# K [* t3 C3 {6 j/ U" y
end
- w* `% Y- r# s, |* A
for i=1:length(P(:,4))" w9 W! F7 l' A! U" Z
plot(x(1,Pp(i,1:2)),y(1,Pp(i,1:2)),'r');
& A1 s1 o; w8 M! O
end
6 ^4 T* q, j. X, X9 m
text(-0.35,-1.2,['最小生成树的权为','',num2str(Wt)]);( }- w0 Y/ N! @8 j7 \* Q% j5 l9 ~9 v
title('红色连线为最小生成树');
6 `: L: @6 v/ v
axis off;
. p7 m1 i5 V& ]
hold off;

复制代码