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

2744557306

通用代码

1. function [result]=myprim(a)//a为传入的每个点的距离矩阵
     [# {& x5 f0 i/ u' e4 t
2. result=[];//用result（3×n）矩阵来表示，第一行表示起点，第二行表示终点，第三行表示权值% m7 X7 _' E  m' t6 Q4 E( j' D! _- [
   
3. p=1;tb=2:length(a);1 k2 l. l0 V# [. X) b# I& F- B
   
4. while size(result,2)~=length(a)-1, i7 s! X+ H* Z( y
   
5.     temp=a(p,tb);temp=temp(:);1 Y1 l' D. g2 B7 G* p8 o9 R# L
   
6.     d=min(temp);
   ! H; ?- G( `  F+ g4 p* K5 ?5 |
7.     [jb,kb]=find(a(p,tb) == d,1);9 O9 S5 {\" E5 k7 H/ K) m
   
8.     j=p(jb);k=tb(kb);6 j  E+ r6 P& r  f7 c% q1 x
   
9.     result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];
   2 \& }5 q. A5 t5 D
10. end
    ! u, t7 d, P0 R$ Z: C3 b

复制代码

怎么看result

我怕有些同学想用这个代码，看不懂result里面元素什么意思，在此提示
, _+ Q6 C) v! Tresult第一行表示起点，第二行表示终点，第三行表示权值
) a% }# [0 n- F例如
1 m8 ^1 y$ R( A* k9 H& tresult =

1. 1     2     5     4     4     75 r  L( z* I6 _) E6 D' \+ |
   
2. 2     5     4     6     7     3
   + c7 S$ T; ]/ R; w
3. 50    40    10    30    42    45
   + A6 J, T& h0 e% V: r1 m
4. 起点就是1，终点是2距离50. i1 Q  K2 E- U1 ?5 Z% c% w3 q
   
5. 然后从2，到5距离400 `( P; B4 V3 a\" T: y0 e
   
6. 从5到4距离100 \1 C# k) H9 W# F& y  A
   
7. 从4到6距离30
   \" K6 ?& U/ Z/ ^4 T' ?- M( I  I
8. 从4到7距离42
   . m1 {\" P% W4 g1 p, q  l
9. 从7到3距离45
   . `# P. H1 D: ]! ]6 {
10. 最后生成完一整棵树
    ( d! ^/ X9 s9 F0 Q5 k; q' l+ _! i, \

复制代码

' ]+ _- n2 L. g