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

function [Wt,Pp]=mintree(n,W)3 p# m5 P1 I9 G! s7 `/ y7 W+ J
%求最小生成树，n为顶点个数，W是权值邻接矩阵，不相邻的用inf表示
5 k6 J* T( c; i
%Wt是最小生成树的权，Pp（：，1：2）表示最小生成树的两顶点
& L3 N) J4 w! ^% @% }8 E
%Pp(:，4)表示最小生成树的序号
1 x. d2 Q+ b# E2 ?0 t
tmpa=find(W~=inf);& R! L# j: b: c+ D
[tmpb,tmpc]=find(W~=inf);
8 x% t2 x5 D1 L6 Z, i9 V+ e
w=W(tmpa);/ T ~$ @! m2 z1 U6 s% l+ M
e=[tmpb,tmpc];
' F" L) X$ a& }3 A
[wa,wb]=sort(w);- r& R8 _( D% j3 P+ K. Q% y
E=[e(wb,:),wa,wb];
& \! |+ ~! L" T9 z
[nE,mE]=size(E);
1 a. ~$ Y, X# g
temp=find(E(:,1)-E(:,2));
3 g0 W: ?1 r c1 u# c9 s
E=E(temp,:); v2 b$ T. O" I6 o! T
P=E(1,:);
- u1 @+ A* [7 W5 s8 C: I
k=length(E(:,1));" O9 p! f+ t) Q
while rank(E)>0
7 G5 t7 X& I! B$ _7 w9 ^6 E
temp1=max(E(1,2),E(1,1));! S( C3 W- `& X* l% n5 @
temp2=min(E(1,2),E(1,1));7 d9 v/ w0 p! [# u
for i=1:k
, w/ Z: E- ^( ^4 ]" w; P$ g' D
if E(i,1)==temp1. f, @* H2 P/ }6 V
E(i,1)=temp2; @+ x, d" }2 h" R, e) Y
end7 _2 W. I) D5 t' C" }* s8 g
if E(i,2)==temp14 @* k) z' Z% g
E(i,2)=temp2;7 ~) y* _& D. I$ q( n
end5 ^& \6 D# b L+ J* B$ F! V
end/ O b4 z% w: M, y
a=find(E(:,1)-E(:,2));
9 o3 P, V- a' C6 j8 D
E=E(a,:);" } d8 I+ \ Y
if rank(E)>02 G: L Z U7 D7 U6 L2 v) B
P=[P;E(1,:)];
# {+ x! r4 k- [6 ~/ j7 j$ r
k=length(E(:,1));
9 q; r9 `2 o/ q0 G
end: `8 t3 Q5 G2 m* r, e7 F
end% {4 D# Q% ]) O
Wt=sum(P(:,3))+ x+ y3 t- L( b1 w% h$ C
Pp=[e(P(:,4),:),P(:,3:4)];8 k. R( v( Q' d( Y
for i=1:length(P(:,3))
3 u5 q, Z- a3 Q$ J( h
disp(['','e',num2str(P(i,4)),'',...4 I5 ^5 x5 C/ p8 ]% \
'(v',num2str(P(i,1)),'','v',num2str(P(i,2)),')']);* l! g7 ~+ c$ S$ }7 C9 C1 k
end
1 [ t3 F9 R* ~3 d8 Z2 ^! _
axis equal;%画最小生成树 8 E1 J& r* E! l. Z% v& r
hold on
" \9 ]: n) u1 y6 \
[x,y]=cylinder(1,n);; G9 L* \6 }9 B# L& B
xm=min(x(1,:));7 k) s }! j7 C9 d. H- s) i8 }
ym=min(y(1,:));
( C- V4 D: N6 ]! R0 z) ]! Y8 u) x
xx=max(x(1,:));( x' u# G, d# v) e. f' [
yy=max(y(1,:));& q& B S; x C9 j" ~4 h) O# X2 Q0 [6 ^
axis([xm-abs(xm)*0.15,xx+abs(xx)*0.15,ym-abs(ym)*0.15,yy+abs(yy)*0.15]);
- D/ W! ?# F7 s
plot(x(1,:),y(1,:),'ko');
( R+ v% B& o! D$ }7 T
for i=1:n2 ]* D! V4 V1 V8 t) L3 C. `
temp=['v',int2str(i)];' k1 q* z, U* E
text(x(1,i),y(1,i),temp);
# N6 [) |% q4 i" u2 e" k; N
end( |6 @- c: f3 C; \. K( c0 ^4 C' Q
for i=1:nE* f9 c9 f& g$ D" N6 {7 t7 u
plot(x(1,e(i,:)),y(1,e(i,:)),'b');
; o% d+ i$ l. A& J+ u* [% {) q
end
' y8 A- N& U! X, a4 M) X+ f
for i=1:length(P(:,4))4 }* k# g4 S, H
plot(x(1,Pp(i,1:2)),y(1,Pp(i,1:2)),'r');
" G: ?, r4 _* O! H1 l* f6 G
end+ `6 T$ V' \) R+ e) O/ S
text(-0.35,-1.2,['最小生成树的权为','',num2str(Wt)]);
7 `( J, B# N7 C6 Y* U
title('红色连线为最小生成树');/ c7 L0 u M3 w8 q( {
axis off;5 r: B5 x8 I# j- a7 H6 V9 A
hold off;

复制代码