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

function [Wt,Pp]=mintree(n,W)& b# r9 r7 l: a
%求最小生成树，n为顶点个数，W是权值邻接矩阵，不相邻的用inf表示% b1 ^5 e, E; V7 S5 Y
%Wt是最小生成树的权，Pp（：，1：2）表示最小生成树的两顶点6 |7 j7 c$ m( _. M/ \! R" v$ D% l
%Pp(:，4)表示最小生成树的序号. u, x5 ^1 R8 v/ b- k T, ~, S- B
tmpa=find(W~=inf);
0 B+ U1 h+ D7 W, a
[tmpb,tmpc]=find(W~=inf);
/ ?& X: U; Z( ]2 F
w=W(tmpa);
$ p! S4 k- e5 B) u ]7 W
e=[tmpb,tmpc];% ^+ Z/ ?& E. t- i/ X9 k
[wa,wb]=sort(w);* F2 K: P# t& X& T
E=[e(wb,:),wa,wb];7 @7 O$ d/ m1 a5 S9 w' i: j9 \$ y
[nE,mE]=size(E);6 j: A7 ?/ \! ]1 C
temp=find(E(:,1)-E(:,2));
$ E: T5 A1 L! S# Z' `+ x6 U
E=E(temp,:);( J% g1 s% U, X$ Z' n- e: W: V- p: U
P=E(1,:);6 ^+ R2 y- K" v. E1 P) s
k=length(E(:,1));* ~/ k. b& B! k6 f
while rank(E)>00 H; L8 R j# F3 y* ]
temp1=max(E(1,2),E(1,1));
! N9 X% I- Y& \0 w, J: {/ S, y# }
temp2=min(E(1,2),E(1,1));5 P% T0 H; G% b( e* Z( e8 _
for i=1:k0 F% W+ W9 j) v# L! Y. h+ K
if E(i,1)==temp1+ D2 o) c) I1 _$ k
E(i,1)=temp2;% W9 {9 _( \! t5 q" k3 s+ b
end
( d, ]4 |7 j& I
if E(i,2)==temp1: @. X N! |0 K' O
E(i,2)=temp2;0 `) q: k+ j; X6 Y
end# W$ V; J' R4 N: W
end
$ j, A/ o S& D# a" `
a=find(E(:,1)-E(:,2));* N* Q* q% g, q- d4 H
E=E(a,:);
+ B: h. H( @" v2 g6 t: S X
if rank(E)>0
" i( J. W ^0 Y# i! p2 V% r: z9 _
P=[P;E(1,:)];
. B' g! o+ Z5 S4 \8 u
k=length(E(:,1));9 _: N1 [4 T! k
end
% s- i& ^" e6 x6 M8 y6 ]6 P1 ^
end' s4 G% F) e2 z. L. k
Wt=sum(P(:,3))! v3 o* _. s8 l
Pp=[e(P(:,4),:),P(:,3:4)];
! K# @ _. }" \1 h4 E8 |
for i=1:length(P(:,3))
! a( }' `7 H( C$ Z( ^; b
disp(['','e',num2str(P(i,4)),'',...
5 q$ ]4 I- [' B" N" S
'(v',num2str(P(i,1)),'','v',num2str(P(i,2)),')']);! n& Z) q* l( Q; ?# q) i ^+ L
end
: e) y" U8 Y2 s& ^- N
axis equal;%画最小生成树
1 N8 o& r; B1 K# b
hold on" R% |* ?1 b1 V4 A9 z$ O
[x,y]=cylinder(1,n);2 d9 i( S5 b/ o# I2 |( e
xm=min(x(1,:));
8 y3 j1 D G$ U6 e& t
ym=min(y(1,:));$ @" { d8 Y4 z
xx=max(x(1,:)); s" T) l0 a) ?, u0 M
yy=max(y(1,:));8 t$ x$ u* n) S0 \
axis([xm-abs(xm)*0.15,xx+abs(xx)*0.15,ym-abs(ym)*0.15,yy+abs(yy)*0.15]);
7 Y2 H5 N: V, j" d/ ]
plot(x(1,:),y(1,:),'ko');
7 `0 s `8 A% r! n9 p4 A( q- D
for i=1:n
1 ]/ u( N [6 P4 G
temp=['v',int2str(i)];5 l/ _0 T/ p! T
text(x(1,i),y(1,i),temp);/ a4 k0 p% Y* s8 I
end
+ \& R6 z1 c, _& |( O: R
for i=1:nE
# |3 e" s& P! c- `, f, G
plot(x(1,e(i,:)),y(1,e(i,:)),'b');
/ p' E7 d2 W; P0 w; r
end
6 _( u; |! h0 E9 m$ B4 `( T G
for i=1:length(P(:,4))
$ n6 j/ ]1 b h1 V8 Q# K0 _
plot(x(1,Pp(i,1:2)),y(1,Pp(i,1:2)),'r');* ?, W# {8 c; z) E' R# N
end1 u) ^+ B3 Z4 c4 \9 i
text(-0.35,-1.2,['最小生成树的权为','',num2str(Wt)]);
, s! U' T& R0 A2 `+ |
title('红色连线为最小生成树');
! b0 S. p. b8 o1 Y0 c$ R& J
axis off;7 p: o7 Y" J5 e1 t
hold off;

复制代码