最小生成树 matlab的图形显示

李芳

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

Edgar_Allan

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

专属雨天

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

madio

1. function [Wt,Pp]=mintree(n,W)
   3 p; X+ b  j2 V/ g3 B1 H; P
2. %求最小生成树，n为顶点个数，W是权值邻接矩阵，不相邻的用inf表示* g* W' W( N1 G
   
3. %Wt是最小生成树的权，Pp（：，1：2）表示最小生成树的两顶点. p6 b8 Z8 z% d; l
   
4. %Pp(:，4)表示最小生成树的序号
   - ^+ [, h' e. J) Z  ?( \8 _( |
5. tmpa=find(W~=inf);
   + u; T( ?1 [8 m7 i
6. [tmpb,tmpc]=find(W~=inf);' z5 }( j1 V5 i& }8 m! @  o: h
   
7. w=W(tmpa);
   . t! N0 v; B; a; \) p1 g% ~
8. e=[tmpb,tmpc];/ E2 T% a2 o, Q  x
   
9. [wa,wb]=sort(w);
   ! p* y2 U0 ?( v
10. E=[e(wb,:),wa,wb];
    ; }1 V$ x' ~- z3 X. G
11. [nE,mE]=size(E);
    8 Y4 p) L5 L* ~
12. temp=find(E(:,1)-E(:,2));. [# c: Y$ V9 f9 f& F: ~9 @
    
13. E=E(temp,:);( h3 q( v# a! {8 c( y9 W  e
    
14. P=E(1,:);, D2 D( E( ~6 h$ I1 I  b2 {! U( ?
    
15. k=length(E(:,1));
    - P1 h9 g+ Y9 V  J- N$ L
16. while rank(E)>0- v8 t  q. p+ D1 n
    
17.     temp1=max(E(1,2),E(1,1));
      o# t! s' w4 p, J8 W
18.     temp2=min(E(1,2),E(1,1));- d* _; n/ U+ \7 }9 N8 A
    
19.     for i=1:k
      L3 c  s# ]- B% H4 V& x
20.         if E(i,1)==temp1* c: K& V4 Q8 r0 E
    
21.             E(i,1)=temp2;$ E0 |; b$ g* V6 P: r: U3 g
    
22.         end
    3 o+ e( ]$ G0 G6 s6 v% a
23.         if E(i,2)==temp1
    - ?9 H\" N# m8 ?$ i1 j* F
24.             E(i,2)=temp2;/ h3 @; O- A( X0 m4 }
    
25.         end
    \" d1 b5 C  k, H+ M3 ?\" d8 q8 j2 S
26.     end
    4 ^7 b( [- ]3 d$ Y  C  h
27.     a=find(E(:,1)-E(:,2));
    $ w# s/ R/ b6 I; ^; R4 @
28.     E=E(a,:);
    4 p% Y: u' e% v0 |
29.     if rank(E)>0
    & }; o* k7 ^\" X\" c' ^3 V- x! d( t$ t0 m
30.         P=[P;E(1,:)];
    0 U' U6 u+ X) i1 j' u
31.         k=length(E(:,1));
    . \: F7 D9 Q, r3 d4 _
32.     end
    0 e7 j; }  i; E
33. end' @6 q1 @/ G3 {\" c6 j
    
34. Wt=sum(P(:,3))5 o3 A1 y: D8 y1 P3 l
    
35. Pp=[e(P(:,4),:),P(:,3:4)];& R* P, f. C2 x; y/ a  y
    
36. for i=1:length(P(:,3))5 l; N, I/ M0 h\" |8 a! s) F
    
37.     disp(['','e',num2str(P(i,4)),'',...8 z2 _2 o* j- H% J
    
38.         '(v',num2str(P(i,1)),'','v',num2str(P(i,2)),')']);1 d6 _\" o9 n  Z$ {% w
    
39. end
    . e$ @6 c* V! b( E: O- ]: b4 y\" ?7 P
40. axis equal;%画最小生成树   
    ) @* j! O. U3 j8 p/ ?! x
41. hold on
    $ {8 M* }3 J; p' ^
42. [x,y]=cylinder(1,n);6 H8 i- R  M8 ?: ?
    
43. xm=min(x(1,:));
    * E7 B6 j% m1 e0 p% L) `$ r  Z
44. ym=min(y(1,:));: p. `* ?( g$ l# M, H% i
    
45. xx=max(x(1,:));
    ; ^9 q& `6 |3 T% h  v
46. yy=max(y(1,:));' n0 h' t' F: `7 D! F2 j
    
47. axis([xm-abs(xm)*0.15,xx+abs(xx)*0.15,ym-abs(ym)*0.15,yy+abs(yy)*0.15]);
    ' U3 i* L% ^( r1 P6 l* m
48. plot(x(1,:),y(1,:),'ko');
    # q5 _& Y+ g7 G5 ~/ \! S. \
49. for i=1:n, k- K: u; o( f* n9 o
    
50.     temp=['v',int2str(i)];4 d( R) D! d. k\" t- z
    
51.     text(x(1,i),y(1,i),temp);\" Z7 M1 R1 K1 j
    
52. end
    6 v% K- J/ J* l% ?% }
53. for i=1:nE
    % S7 \3 P7 [  D9 M
54.     plot(x(1,e(i,:)),y(1,e(i,:)),'b');! u6 W8 V1 ]1 ~  Q# `7 c0 `
    
55. end3 `& N1 E  c5 ?7 ^  z2 I: j
    
56. for i=1:length(P(:,4))* L\" k* {8 i; u5 B& G, o
    
57.     plot(x(1,Pp(i,1:2)),y(1,Pp(i,1:2)),'r');
    5 e$ Z\" J# ?/ w* h
58. end9 X6 D2 N3 @/ h8 Z& g4 Q' R5 Q2 y0 `
    
59. text(-0.35,-1.2,['最小生成树的权为','',num2str(Wt)]);
    + p0 \0 u$ L! V3 @0 S/ }
60. title('红色连线为最小生成树');2 u2 S4 f0 b) ]
    
61. axis off;
    & J, Z  h\" c1 j+ D$ B# X. g5 {
62. hold off;

复制代码

这个函数可以实现，现在matlab中建立m文件mintree.m，然后就可以在命令行调用它了。
下面是一个调用的例子：我们来画下面问题的最小生成树：

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)
生成的结果是：Wt =
0 h& Y6 b1 B% Y+ H* @) Q1 B    69

e2(v2v1)
e13(v5v3)
e4(v3v1)
: v2 L% h4 U0 `6 ~/ Ce18(v7v4)
e17(v6v4)
e12(v4v1)

# ?8 A1 K) T8 V9 p! F! Jans =
7 }2 N4 P) d1 \
    69
- [1 N  I0 }2 S; n+ W

- V6 [& o" c7 c# f: f