最小生成树 matlab的图形显示

李芳

如何在matlab中用图形显示最小生成树 求代码 希望得到高人的指点

madio

1. function [Wt,Pp]=mintree(n,W)
   6 Y- Q% J5 S$ S8 G. N
2. %求最小生成树，n为顶点个数，W是权值邻接矩阵，不相邻的用inf表示
   & z- O& A: y8 X$ R) B- ?
3. %Wt是最小生成树的权，Pp（：，1：2）表示最小生成树的两顶点, [* `! z* t9 m0 K2 X
   
4. %Pp(:，4)表示最小生成树的序号
   % _\" y9 {9 |0 e. E: P/ @
5. tmpa=find(W~=inf);
   7 Q) \% s& p0 p* H# S
6. [tmpb,tmpc]=find(W~=inf);
   3 O: A# O' H% ?  M. z9 T
7. w=W(tmpa);/ o+ w* ~: k! K+ P
   
8. e=[tmpb,tmpc];$ i9 N' B5 u8 T9 g# I
   
9. [wa,wb]=sort(w);
   ! W1 ]: E. ]; C
10. E=[e(wb,:),wa,wb];6 b' N$ o. p0 n8 J
    
11. [nE,mE]=size(E);$ X9 v* G) s, p0 E! ]
    
12. temp=find(E(:,1)-E(:,2));
    6 b2 v4 M$ p\" h# i* C) r( }
13. E=E(temp,:);
    ) I% @7 q6 ?4 x: t2 T5 N
14. P=E(1,:);
    1 @/ ^4 U: R9 y# D4 a2 ?' c
15. k=length(E(:,1));
    ! b$ y* o- ^6 J
16. while rank(E)>0
    4 k\" ?8 A0 z- I: d6 q/ y\" j
17.     temp1=max(E(1,2),E(1,1));9 h: C5 M, I  x/ V: N
    
18.     temp2=min(E(1,2),E(1,1));. t9 S' w6 i1 {# }9 z; I8 `
    
19.     for i=1:k
    ) K+ v: Q) e& c9 ^; e. ^3 y+ S
20.         if E(i,1)==temp1, \  W; V5 d! s7 E
    
21.             E(i,1)=temp2;
    & B1 O5 j* \# {9 h/ S  R! i\" Q
22.         end
    # Y+ F8 d% w' F; f
23.         if E(i,2)==temp1- r0 m3 X2 }3 x5 Q- r
    
24.             E(i,2)=temp2;
    5 u' V/ n% k) q8 o9 G8 _
25.         end& Q, ~$ S: u1 l# @% d- c: g
    
26.     end. \2 R6 L$ T\" u' N, S
    
27.     a=find(E(:,1)-E(:,2));9 E  F\" A  o! N. x7 v' j
    
28.     E=E(a,:);0 Y$ E0 G. f+ Y2 z) _( u9 B- @
    
29.     if rank(E)>0
    ; A3 ?* W% Y: g  S) F5 b
30.         P=[P;E(1,:)];8 \. \6 ~, B5 e
    
31.         k=length(E(:,1));: h1 w% \7 V. @% X* V2 S
    
32.     end
    9 n! ?0 E, P: v- Z* {6 b
33. end7 N1 P. G! `8 K: I- V8 E. e! T
    
34. Wt=sum(P(:,3)). ^1 K8 f8 q\" h. t0 v
    
35. Pp=[e(P(:,4),:),P(:,3:4)];
    5 J# _; v; J0 w# T4 H2 n
36. for i=1:length(P(:,3))6 _; c. g. ^- [! l
    
37.     disp(['','e',num2str(P(i,4)),'',...1 B' F* W0 _& q; w7 w  T! H5 o6 F4 A
    
38.         '(v',num2str(P(i,1)),'','v',num2str(P(i,2)),')']);9 ~; b$ `8 L3 D& p
    
39. end
    ! _) L/ o/ L% [, N
40. axis equal;%画最小生成树   
    $ v* T7 G- s& X
41. hold on3 G7 `, }5 e9 d9 @7 L% B$ `3 x. \
    
42. [x,y]=cylinder(1,n);
    + g4 U6 Y( [$ n4 P& ?; L
43. xm=min(x(1,:));
    / r- f3 F0 U7 t7 H. o
44. ym=min(y(1,:));5 w& Y6 r/ J9 I% K
    
45. xx=max(x(1,:));
    3 Q  V& A0 p2 k/ s8 q5 T
46. yy=max(y(1,:));
    - H5 `* ]2 }, e5 x' y) C1 J
47. axis([xm-abs(xm)*0.15,xx+abs(xx)*0.15,ym-abs(ym)*0.15,yy+abs(yy)*0.15]);5 @, k. t# s: S2 q\" G9 Y' C
    
48. plot(x(1,:),y(1,:),'ko');
    2 d6 e7 H* w( |' [) g
49. for i=1:n
    ; d) x\" ~- }& V2 f
50.     temp=['v',int2str(i)];
    ) m& s6 d# c$ {( R
51.     text(x(1,i),y(1,i),temp);
    # a; ~+ T0 j; D# s. ~! e
52. end$ s# v  f3 j! B6 u2 Q9 x
    
53. for i=1:nE4 @\" R  A$ |' ?2 k; u
    
54.     plot(x(1,e(i,:)),y(1,e(i,:)),'b');8 @2 Y% ?+ Q; h/ d5 x1 y& O. Q
    
55. end
    4 M; J8 G# @* K
56. for i=1:length(P(:,4))
    . O/ C! d2 ^# H+ Q( W( |
57.     plot(x(1,Pp(i,1:2)),y(1,Pp(i,1:2)),'r');
    0 k- e& K5 _& W: M
58. end2 H5 V6 I7 z3 r/ U4 T
    
59. text(-0.35,-1.2,['最小生成树的权为','',num2str(Wt)]);+ k* \$ L$ h% E; |; o  h
    
60. title('红色连线为最小生成树');
    7 Y7 {1 `- L2 Q! Z9 c5 `
61. axis off;, A0 e- U. U' k/ H0 r$ J
    
62. hold off;

复制代码

这个函数可以实现，现在matlab中建立m文件mintree.m，然后就可以在命令行调用它了。
# A# B! J( n; g7 `4 k# N下面是一个调用的例子：我们来画下面问题的最小生成树：

matlab命令行代码为： A=[0 4 15 inf 7 inf 28;4 0 9 inf inf inf inf;15 9 0 25 5 inf inf;inf inf 25 0 32 16 12;7 inf 5 32 0 inf 30;inf inf inf 16 inf 0 20;28 inf inf 12 30 20 0]；mintree(7,A)
+ S1 _- L. g3 `生成的结果是：Wt =
    69

e2(v2v1)
e13(v5v3)
e4(v3v1)
7 I0 x( ^8 q/ `3 Ne18(v7v4)
e17(v6v4)
& s, K) ~/ g; v" ~3 r5 @+ n$ b2 qe12(v4v1)

ans =

    69

* q0 n  ~2 ~& h

专属雨天

顶--------------

Edgar_Allan

那如果要树支型的要怎么改呢？谢谢了