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

function [Wt,Pp]=mintree(n,W)
7 ?# ?, D+ H, R. u; @2 i- B
%求最小生成树，n为顶点个数，W是权值邻接矩阵，不相邻的用inf表示/ D% c) M! J9 {8 a/ }% Y3 s
%Wt是最小生成树的权，Pp（：，1：2）表示最小生成树的两顶点( o! d8 E7 t) i. J3 {5 z7 e
%Pp(:，4)表示最小生成树的序号# s+ Z' o4 g/ u& e
tmpa=find(W~=inf);3 m+ O1 ?) I' P. ^' ~' x' ~/ }
[tmpb,tmpc]=find(W~=inf);2 ^7 L3 I2 l8 p. X* E1 `0 j
w=W(tmpa);
. p: X8 `! T l% {0 Y. P! i
e=[tmpb,tmpc];
# t* q8 `* O3 D/ J0 l3 D8 Q
[wa,wb]=sort(w);
: @( v5 S& C |
E=[e(wb,:),wa,wb];
3 v5 h( S8 K" D. J
[nE,mE]=size(E);! ^4 L, J5 ?5 c
temp=find(E(:,1)-E(:,2));
, W8 h* P1 K9 j/ v, y: z2 u
E=E(temp,:);9 T A: c- O% h' _* X
P=E(1,:);0 P4 c- E5 c5 Z. @& D
k=length(E(:,1));
' g: a/ n9 Q; L9 @
while rank(E)>0
s- u% w+ h/ c" k
temp1=max(E(1,2),E(1,1));
: Q" U0 x! X# l9 o" E- ~
temp2=min(E(1,2),E(1,1));- V$ X9 E; i' }. q
for i=1:k6 Z5 j" `6 p2 t8 V$ u- ^6 Z
if E(i,1)==temp1$ L3 C/ Z/ P. X) b( S9 W" ?
E(i,1)=temp2;: G# M, D/ b2 D% j7 C6 c
end
! G: V" F, Z( w9 o: o6 v) Q
if E(i,2)==temp1& `$ y) h- _% K* ]% y7 J) C
E(i,2)=temp2;
0 K# m; e% Z2 T& F% j+ u
end
" v& ~+ M' F4 b7 z( Z& R9 Z
end
* z: y/ T5 H' E/ H; u2 ]2 s
a=find(E(:,1)-E(:,2));
* G! d: b; J$ H* [
E=E(a,:);
# g' E8 o5 L+ Z, D
if rank(E)>0
2 l$ P# C4 G6 n' {9 C
P=[P;E(1,:)];
8 `7 g( s2 h& ~, w4 d" [+ P$ y' `
k=length(E(:,1));7 p. b: c$ \# D3 V y( y/ m
end
& R3 ~( U) {( I; p0 R! @
end
0 i2 ^; K Y6 D% T# ~8 `6 P
Wt=sum(P(:,3))
$ w [% U3 P* y( Z$ s; @) n8 E
Pp=[e(P(:,4),:),P(:,3:4)];
5 T* G; I. B. T6 Q# F
for i=1:length(P(:,3))5 Z" z7 @- e/ h4 D [) V
disp(['','e',num2str(P(i,4)),'',...8 E4 v; U! T' c; C
'(v',num2str(P(i,1)),'','v',num2str(P(i,2)),')']);
2 j% m2 @9 h" `1 o4 Q) o7 R6 c0 [$ O
end
@0 O* N, g: Y; d* T! T' d; M2 o
axis equal;%画最小生成树 8 e) u4 Y8 d- D Q' u3 ~
hold on7 V/ t9 X3 y3 m+ L
[x,y]=cylinder(1,n);% i4 W8 m, \! x+ p
xm=min(x(1,:));& w2 }. y; D, a3 B' ], R9 |
ym=min(y(1,:));
- ^; G# Y( Z% L! r
xx=max(x(1,:));4 s) a5 D8 F3 a, |! }7 s) o5 W
yy=max(y(1,:));
. e$ ]) D$ L" D2 M
axis([xm-abs(xm)*0.15,xx+abs(xx)*0.15,ym-abs(ym)*0.15,yy+abs(yy)*0.15]);
0 j$ d8 t& q. g1 O
plot(x(1,:),y(1,:),'ko');/ q+ Q4 O, `- c% H7 D
for i=1:n, ?$ n; S l; r- I
temp=['v',int2str(i)];) U; L/ t$ \: M# `; Z
text(x(1,i),y(1,i),temp);- L7 Y+ f0 T }7 D, C5 @
end
- I0 q5 l6 c! U/ K
for i=1:nE4 k0 U9 R5 \7 { e
plot(x(1,e(i,:)),y(1,e(i,:)),'b'); N, O. C! y% _3 G
end$ X/ m- w# ?& q9 v9 G* P, j5 f
for i=1:length(P(:,4))
% I( a6 L& L. w$ N! I7 r, x9 c
plot(x(1,Pp(i,1:2)),y(1,Pp(i,1:2)),'r');# r# {2 M+ R" {
end4 }8 V4 @" v( X) b1 o) w* O. P0 `
text(-0.35,-1.2,['最小生成树的权为','',num2str(Wt)]);
6 L! `' m; l8 U5 y$ r
title('红色连线为最小生成树');4 ?9 q1 K3 y; _* p% W
axis off;
$ Q0 u# y; s' N: E1 ]
hold off;

复制代码