数模：最小生成树prim算法（通用matlab代码）

2744557306

通用代码

1. function [result]=myprim(a)//a为传入的每个点的距离矩阵& F* Q, M5 E' G! l( u# t\" H
   
2. result=[];//用result（3×n）矩阵来表示，第一行表示起点，第二行表示终点，第三行表示权值
   & E/ Q2 V0 p, k+ h- D/ v9 n
3. p=1;tb=2:length(a);9 h* w. }) E4 r& R
   
4. while size(result,2)~=length(a)-1
   + o. n. `5 Z8 @2 W+ M\" O1 W0 w
5.     temp=a(p,tb);temp=temp(:);
   7 h; Q) Y/ t. `$ S1 q& p. y8 O9 L
6.     d=min(temp);
   ! K3 T4 M' A  m4 W
7.     [jb,kb]=find(a(p,tb) == d,1);+ c( Q5 J\" {+ h$ C0 O& L. k) D
   
8.     j=p(jb);k=tb(kb);
   % _; J( M5 R( t' B3 m' ~0 u; b0 w
9.     result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];% b- p- w; V# u% U  M+ v
   
10. end+ c, P. H4 Y% S( h( v
    

复制代码

怎么看result

我怕有些同学想用这个代码，看不懂result里面元素什么意思，在此提示
result第一行表示起点，第二行表示终点，第三行表示权值
8 D5 u/ }2 I8 Z3 R8 T# i5 ?6 x) B+ Y8 J例如
result =

1. 1     2     5     4     4     7
   2 t\" G4 e6 w' ]/ u9 l2 L( L
2. 2     5     4     6     7     33 y! U* `3 j2 F
   
3. 50    40    10    30    42    45+ u. ~# w0 ^( I( Z3 d
   
4. 起点就是1，终点是2距离50/ j' E  @6 }; U
   
5. 然后从2，到5距离40
   $ I3 m4 d1 x0 ?. q
6. 从5到4距离10
   & W4 U2 e& V6 g: h
7. 从4到6距离30
   8 ~\" j( S& x. o% h
8. 从4到7距离42# A+ I, g1 h\" S! f9 p% p
   
9. 从7到3距离45
   & [! |& J' i, R
10. 最后生成完一整棵树
    3 }- k3 s$ |/ U8 D* m) _9 u, ]\" E

复制代码

. E) a8 {5 \" W3 x9 P$ b