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

2744557306

通用代码

1. function [result]=myprim(a)//a为传入的每个点的距离矩阵1 c9 |. ], N\" |* O
   
2. result=[];//用result（3×n）矩阵来表示，第一行表示起点，第二行表示终点，第三行表示权值\" b\" f7 w0 q' A$ `/ x
   
3. p=1;tb=2:length(a);
   ( Z' s7 H\" Z/ L5 v/ z6 K6 E\" L6 }* l
4. while size(result,2)~=length(a)-1
   8 t0 ^- E9 S% B/ j+ t$ Z' w
5.     temp=a(p,tb);temp=temp(:);
   $ Q, c, U4 j* b* z) C, `1 E2 ]
6.     d=min(temp);+ b; c4 R1 w  C( t3 ]\" F2 B\" T  `2 q
   
7.     [jb,kb]=find(a(p,tb) == d,1);$ ^8 _9 l0 [0 `' R) R& j$ J7 w
   
8.     j=p(jb);k=tb(kb);3 P) e+ A0 F) r& @1 M5 h
   
9.     result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];/ x+ V0 @  O/ _  `3 H
   
10. end\" U9 H2 M, o3 G+ v
    

复制代码

怎么看result

我怕有些同学想用这个代码，看不懂result里面元素什么意思，在此提示
result第一行表示起点，第二行表示终点，第三行表示权值
- ?: N. k  b4 b' Z8 j+ m例如
0 T" O. _0 P9 ~result =

1. 1     2     5     4     4     7) b. |( m' B4 O/ L1 }; o
   
2. 2     5     4     6     7     3
   / Q! Z% d) R' }3 J  r$ a
3. 50    40    10    30    42    45+ ^* @5 j! G\" e4 P- Y5 Y: `' ]
   
4. 起点就是1，终点是2距离50! c$ u/ _+ ^4 n' R+ o' o0 g5 x
   
5. 然后从2，到5距离40
   \" Z3 `, P; ~6 B! ~% E0 K
6. 从5到4距离10# U' c6 ^- R: e
   
7. 从4到6距离302 O4 R) ~. o4 z\" |) n# x
   
8. 从4到7距离42
   . I% y/ W$ M# J% j' J& O
9. 从7到3距离45
     A0 o3 C1 X9 Q. `0 o, A0 o; _  Q' ?9 w4 `
10. 最后生成完一整棵树
    . _, ]1 r7 `! l5 H# q8 X6 m

复制代码

, C0 R: `4 w* `2 n! T( }. }4 s