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

2744557306

通用代码

1. function [result]=myprim(a)//a为传入的每个点的距离矩阵
   1 s+ ]7 [5 i' J/ G( F- T8 {9 t8 G* T
2. result=[];//用result（3×n）矩阵来表示，第一行表示起点，第二行表示终点，第三行表示权值
   # Z/ N6 A: u/ K+ ^) f0 o
3. p=1;tb=2:length(a);
   9 D. Y- T) V, r$ _
4. while size(result,2)~=length(a)-1' K\" b- z$ }* `0 ~\" g6 o! L
   
5.     temp=a(p,tb);temp=temp(:);7 \8 S% A$ r! z: F: N5 G, K
   
6.     d=min(temp);
   $ k7 k2 z  q, m0 k- L5 b+ T
7.     [jb,kb]=find(a(p,tb) == d,1);  v6 H) |* A3 z/ o
   
8.     j=p(jb);k=tb(kb);
   / f. M# W! w9 @  w- _: G
9.     result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];
   ) U& _- x9 N# c9 U
10. end4 v% j4 d; r) i3 d- a, I+ C
    

复制代码

怎么看result

我怕有些同学想用这个代码，看不懂result里面元素什么意思，在此提示
* K0 r+ W  ?2 Q$ ^result第一行表示起点，第二行表示终点，第三行表示权值
7 D" [, ~: l9 v9 Q5 U* f  Y例如
1 C( S0 V% S: Z/ C% yresult =

1. 1     2     5     4     4     78 R' y7 B/ R: b4 k. }
   
2. 2     5     4     6     7     3
   9 t4 a* c& I9 B& U' t\" J& b& a+ l
3. 50    40    10    30    42    450 H3 n\" z$ B1 G, Z
   
4. 起点就是1，终点是2距离50
   , f' V5 ?5 s: o. ~/ j$ m
5. 然后从2，到5距离40: U* s4 W4 h, \- h
   
6. 从5到4距离10
   3 f, A1 W8 g$ y\" z: p; m
7. 从4到6距离30. D/ i3 B* b& K) H: ]
   
8. 从4到7距离42; ~2 L* M  z7 \1 I\" r
   
9. 从7到3距离452 Q- U6 K! N9 K& P# Z7 A6 m
   
10. 最后生成完一整棵树) }5 r$ a; e) P6 ?* x
    

复制代码