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

function [Wt,Pp]=mintree(n,W)# |- L ]0 p: p, D. v
%求最小生成树，n为顶点个数，W是权值邻接矩阵，不相邻的用inf表示
. V% [) {. n: m5 M# e' X( I& q
%Wt是最小生成树的权，Pp（：，1：2）表示最小生成树的两顶点" H, W; K! A. l1 \, F) a2 m9 f
%Pp(:，4)表示最小生成树的序号
- `; V6 M- g" c9 t$ \2 R6 Y$ u
tmpa=find(W~=inf);
1 y6 g0 S" |% s9 ]5 A
[tmpb,tmpc]=find(W~=inf);: A; G7 }8 e6 U. A+ r
w=W(tmpa);1 }& S$ e3 y9 @. i( ~) i2 K3 {
e=[tmpb,tmpc];2 s2 z0 b1 e$ D
[wa,wb]=sort(w);
2 T, [. x1 w) }+ b) \$ p! ~
E=[e(wb,:),wa,wb];! r: F) {% P6 L) Y2 ]
[nE,mE]=size(E);0 ]+ D9 _/ D' Z" |* j- T
temp=find(E(:,1)-E(:,2));9 Y! E" G; j2 l8 w2 E& i/ t
E=E(temp,:);
* B+ ]+ x) H* t% l. g
P=E(1,:);/ z+ q5 T V4 f" q8 q- o
k=length(E(:,1));
' x7 _1 V1 V/ J
while rank(E)>0
$ }6 `! O! H* q4 m
temp1=max(E(1,2),E(1,1));# Q# F6 s& {- n$ `4 [
temp2=min(E(1,2),E(1,1));! S1 X! m4 x$ g3 `, i. O& ]. |
for i=1:k
9 Q: B# @" O+ E8 K8 i
if E(i,1)==temp14 S5 D: v) x' J8 n: B4 _9 }
E(i,1)=temp2;
1 O7 K- \2 r3 C' D L( o! [' [3 ]
end6 X: D9 M F5 u
if E(i,2)==temp1
% ~" ^6 ^) w9 s& N$ Z
E(i,2)=temp2;' [' f" k0 T1 s. h' L
end
; [" j; J5 D) p* z# g0 P1 A
end
- Z) K6 x5 c7 ?7 F
a=find(E(:,1)-E(:,2));4 ]% h# P- d5 P# o% q6 a
E=E(a,:);
& S, y/ B# C8 n; J
if rank(E)>0+ A; i) c! u+ a* {
P=[P;E(1,:)];6 Z* B: L6 c: f! w$ `* r
k=length(E(:,1));% b: {/ P" b5 Z& K
end
# ]) Z! N) y% q, `; }. o0 |
end
9 Q- p% i. K' c2 ]4 s
Wt=sum(P(:,3))* P# i9 U- b9 R& j" j
Pp=[e(P(:,4),:),P(:,3:4)];' Q9 i. g4 W! e; d& p% X0 J
for i=1:length(P(:,3))
& y& L# O$ D. @6 ~( F) N0 s' p
disp(['','e',num2str(P(i,4)),'',...3 m# R0 l8 r+ ?7 W
'(v',num2str(P(i,1)),'','v',num2str(P(i,2)),')']);% }6 W' Q' ]! G V* S
end
: E! F: L" W& E- s4 J
axis equal;%画最小生成树
6 A# @8 p; Y8 `( @6 b+ v* [
hold on+ E$ u8 @" l; g2 d- R. E
[x,y]=cylinder(1,n);( G) Z) q2 r5 o3 ~6 M
xm=min(x(1,:));
5 u6 {) Z# E: f5 T% u$ W/ Y7 M9 B& w
ym=min(y(1,:));
- a5 j" `2 N4 k7 ?, W- v% y& `" \: z
xx=max(x(1,:));0 F; B/ z, X, w5 W
yy=max(y(1,:));
) _ k$ l6 a# B7 {
axis([xm-abs(xm)*0.15,xx+abs(xx)*0.15,ym-abs(ym)*0.15,yy+abs(yy)*0.15]);
: O" F1 `1 \; f4 _4 Q' _
plot(x(1,:),y(1,:),'ko');/ P0 s& l2 D* ~8 o$ t) I5 s8 v. [
for i=1:n9 h. `9 o' w2 t Q1 X
temp=['v',int2str(i)];
# h, @; {. u. M2 O) G# |
text(x(1,i),y(1,i),temp);
, v; B! _7 k' S" j: t& Q
end1 S* _) T& }' Z" B4 o2 s) o
for i=1:nE, z4 W5 T9 ~7 K% \6 p% u: v
plot(x(1,e(i,:)),y(1,e(i,:)),'b');
. I9 d* X; q6 z; Q6 W0 r! L5 L
end& _' s* F, E( J0 B
for i=1:length(P(:,4)); K* g7 D/ X' U
plot(x(1,Pp(i,1:2)),y(1,Pp(i,1:2)),'r');
/ k% ? D' c" P) F( l7 A
end
7 `9 C! Z$ L2 N _7 a' H
text(-0.35,-1.2,['最小生成树的权为','',num2str(Wt)]);- Q3 ]& |3 z- }8 B) d
title('红色连线为最小生成树');
+ D: E! R5 R& t* o4 o- N
axis off;- F/ o k. \2 T2 t( Q
hold off;

复制代码