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

2744557306

通用代码

1. function [result]=myprim(a)//a为传入的每个点的距离矩阵
   9 w8 W- s# g4 O
2. result=[];//用result（3×n）矩阵来表示，第一行表示起点，第二行表示终点，第三行表示权值) m8 @\" F) P( b
   
3. p=1;tb=2:length(a);
   ) r  R1 \$ X! I5 U
4. while size(result,2)~=length(a)-1
   % V6 L! ^9 X6 Z1 X
5.     temp=a(p,tb);temp=temp(:);/ E3 |$ e1 S0 I2 \( ]
   
6.     d=min(temp);% d' t8 l\" p$ ?$ r- c* i% ]
   
7.     [jb,kb]=find(a(p,tb) == d,1);
   \" P* ?/ U1 ?. h) Y# o; ~
8.     j=p(jb);k=tb(kb);
   8 Y0 E8 ^2 t( [, ]8 B
9.     result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];$ x  K$ X) V# L8 o3 a- j( Y
   
10. end
      v; K/ F* s- H3 x9 ~

复制代码

怎么看result

我怕有些同学想用这个代码，看不懂result里面元素什么意思，在此提示
. |5 v" w- X5 S& p- f5 D9 Aresult第一行表示起点，第二行表示终点，第三行表示权值
! `" U3 v# z: t: m* Q# F, v3 X. C例如
. J1 a& `5 `' [+ U. P& B7 C% Jresult =

1. 1     2     5     4     4     7
   4 L5 y  m. y\" z, q1 C, @
2. 2     5     4     6     7     3
   \" K9 o+ d7 K* j! x/ G3 V
3. 50    40    10    30    42    45! d+ u1 r3 l+ |7 Z. m4 O
   
4. 起点就是1，终点是2距离50' L$ \. H\" Q/ y: w- a
   
5. 然后从2，到5距离40
   \" A0 E6 j) e  i, }6 Q) M* V. y
6. 从5到4距离10
   \" w& Q$ B8 m7 a5 Q9 |  c9 P! Z9 B
7. 从4到6距离30/ _) g. g- c) y) V# t$ w, q8 }
   
8. 从4到7距离42/ q: J- o) Y8 I& t7 @
   
9. 从7到3距离457 Y1 B5 Z$ k- d3 o- r\" V+ v( n# N/ n
   
10. 最后生成完一整棵树) i0 ^% B: ~/ W
    

复制代码

4 W0 o, r# ^+ Q2 H" r! B