最小生成树 matlab的图形显示

李芳

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

madio

1. function [Wt,Pp]=mintree(n,W)
   + F) l& F7 b4 V# T6 {9 _
2. %求最小生成树，n为顶点个数，W是权值邻接矩阵，不相邻的用inf表示: `4 ]3 N( |2 d5 N7 l3 e
   
3. %Wt是最小生成树的权，Pp（：，1：2）表示最小生成树的两顶点
   4 E  x8 t8 Y( W/ e
4. %Pp(:，4)表示最小生成树的序号- M; U2 O% j4 j% W& K
   
5. tmpa=find(W~=inf);
   % g4 N* D( w0 X; [0 X
6. [tmpb,tmpc]=find(W~=inf);% \; }# E0 w% B) L7 F9 Z
   
7. w=W(tmpa);( _/ ~. H; J. o4 u6 _0 E  }5 E
   
8. e=[tmpb,tmpc];/ @# Z+ H- {% p  F$ x$ a\" g; m
   
9. [wa,wb]=sort(w);: s) R) o! J' @- R1 c; A
   
10. E=[e(wb,:),wa,wb];0 F/ V* u- d. a) @; i5 b
    
11. [nE,mE]=size(E);. G+ S2 h' _8 e6 q; e' q
    
12. temp=find(E(:,1)-E(:,2));
    * m8 r4 I- G* k: G( X' {+ ^5 L* |
13. E=E(temp,:);6 p2 N6 }0 U& J4 n8 X! Z! \6 _: d
    
14. P=E(1,:);
      K* `* S! X! X& M4 W7 N\" s
15. k=length(E(:,1));; i8 z! m( M0 i\" ]3 Q
    
16. while rank(E)>08 D% g$ g5 b' |! M  j0 ~2 a9 C6 n
    
17.     temp1=max(E(1,2),E(1,1));* p; L# c# p% w; O4 p; v; g
    
18.     temp2=min(E(1,2),E(1,1));
    ( k, t  S\" Q% L7 z, w
19.     for i=1:k
    . W8 \* T. w% I
20.         if E(i,1)==temp1
    / F, h% L6 Z# B9 {) O/ s4 H' w
21.             E(i,1)=temp2;  E  x\" M\" S. b  Q- V
    
22.         end
    . o0 P0 _# l& _+ e* A
23.         if E(i,2)==temp1! C$ U. u7 E1 @( O, u  s. k9 F
    
24.             E(i,2)=temp2;
    7 }/ B6 {4 Z# H& i# b/ v3 U
25.         end/ ?! ~1 ?# n* l7 J
    
26.     end0 \, ^3 a, v: P; J! V
    
27.     a=find(E(:,1)-E(:,2));
    ) m  @6 x0 z  b6 L
28.     E=E(a,:);
    8 g  q\" ^* O$ |8 w
29.     if rank(E)>0( n\" @' r7 f- f& H* T
    
30.         P=[P;E(1,:)];4 _) J, C8 z! z$ b, Z' b( z
    
31.         k=length(E(:,1));
    # \' w& U3 F8 w# M& A/ ~
32.     end\" J5 `3 `. |$ `) u
    
33. end
    & F! b3 l$ j0 m4 Y\" M
34. Wt=sum(P(:,3))
    5 ]\" {* z2 i; X: N4 v) C0 ^# O8 r6 K
35. Pp=[e(P(:,4),:),P(:,3:4)];  X* ?* C7 f; r6 G( |! M
    
36. for i=1:length(P(:,3))
    % m* ~; \9 c' K# ^/ N' L
37.     disp(['','e',num2str(P(i,4)),'',...
    : C( [8 T7 D. r+ `3 j
38.         '(v',num2str(P(i,1)),'','v',num2str(P(i,2)),')']);4 K: S& Q% A( y: U% C. A( z
    
39. end
    ) B, p$ H1 Y3 }, k
40. axis equal;%画最小生成树   0 \3 i% V. Y. o+ |0 N' i
    
41. hold on
    ) ]4 V: I7 I% |; {  n# \
42. [x,y]=cylinder(1,n);5 ?: D% W6 T* `5 L8 U) t\" s* O
    
43. xm=min(x(1,:));# t: A& `' Q- Y+ `
    
44. ym=min(y(1,:));
    : t& p2 E. ^. X& s
45. xx=max(x(1,:));
    0 O8 q; k$ R9 q) e/ j
46. yy=max(y(1,:));
    ' e: y( X9 t1 p2 L- `; T5 h
47. axis([xm-abs(xm)*0.15,xx+abs(xx)*0.15,ym-abs(ym)*0.15,yy+abs(yy)*0.15]);& Y$ ?9 s8 _$ ^4 N
    
48. plot(x(1,:),y(1,:),'ko');
    7 `: n  [: v/ D& S0 S6 Y\" ~2 k
49. for i=1:n3 D- {- B( [5 [; @
    
50.     temp=['v',int2str(i)];, g$ J4 R- h4 ?7 V+ W9 h* A
    
51.     text(x(1,i),y(1,i),temp);
    ) \! L9 }\" W% [  I  L
52. end, l( B6 D; z1 F. T: i$ z( i
    
53. for i=1:nE
    ' p) ?9 w7 X* ^6 e1 O
54.     plot(x(1,e(i,:)),y(1,e(i,:)),'b');
    9 n6 e3 f5 `4 ]* p. n$ P
55. end. B9 k5 n/ i4 ^, a; E
    
56. for i=1:length(P(:,4))
    & J5 J8 J, |9 b% h! n
57.     plot(x(1,Pp(i,1:2)),y(1,Pp(i,1:2)),'r');
    ( L9 p& H+ Y) h, R
58. end- t' t5 c1 B! V4 M
    
59. text(-0.35,-1.2,['最小生成树的权为','',num2str(Wt)]);
    9 s  A, \7 E  D+ x) u
60. title('红色连线为最小生成树');
    * I# p4 x9 R5 Y1 `* p' a  E5 s6 g& M
61. axis off;0 A% m8 ~- l: {1 x! ]! i6 n4 v2 \
    
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 =
! \8 z- l1 f& E- m; Z- g& u! Z/ v    69

e2(v2v1)
e13(v5v3)
e4(v3v1)
e18(v7v4)
e17(v6v4)
' @: N3 C8 p1 W+ C# Pe12(v4v1)
8 S6 w" U. y1 X* R8 v! V% u( D
2 b+ @# L1 `, D: D! ^3 bans =

  w, I) I% e5 q  g9 q3 g    69

专属雨天

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

Edgar_Allan

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