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

2744557306

通用代码

1. function [result]=myprim(a)//a为传入的每个点的距离矩阵
   - ^1 Y* l, J1 h* }( h  R! d
2. result=[];//用result（3×n）矩阵来表示，第一行表示起点，第二行表示终点，第三行表示权值4 n: s( a; ]0 ~: Q4 F: t2 G. ]
   
3. p=1;tb=2:length(a);
   \" E/ T6 c& `* G5 X  B
4. while size(result,2)~=length(a)-1* S/ g  v7 k' G3 U- x
   
5.     temp=a(p,tb);temp=temp(:);' ~6 t( X8 R& @& g0 f% ]6 ?
   
6.     d=min(temp);4 P) a/ ~. s5 ~) P2 D& k$ O
   
7.     [jb,kb]=find(a(p,tb) == d,1);
   , m9 L/ \/ G7 v6 j6 u' w
8.     j=p(jb);k=tb(kb);
   ' `8 r1 ]$ `/ X; \; c0 }* ?* c
9.     result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];
   / n. d2 L4 z1 O! p' J
10. end/ O4 ?5 N% a. n' x
    

复制代码

怎么看result

我怕有些同学想用这个代码，看不懂result里面元素什么意思，在此提示
result第一行表示起点，第二行表示终点，第三行表示权值
例如
$ Z5 P0 S2 b# S  s8 Nresult =

1. 1     2     5     4     4     7\" W3 p) e$ E6 S( |. x4 }$ W
   
2. 2     5     4     6     7     3
   + s; N' x1 Q9 y4 E5 e. o
3. 50    40    10    30    42    45\" m9 m& I: E: d  Q$ p# q
   
4. 起点就是1，终点是2距离50
   : v+ P$ T; e; b5 n# U' a# a$ y6 W- V& }
5. 然后从2，到5距离40* _3 |& Q$ x9 Y4 J
   
6. 从5到4距离10; b9 T7 ~2 W& U5 g4 h
   
7. 从4到6距离30& `; f9 y/ B& I% U
   
8. 从4到7距离424 t$ f% D; {* y\" Z\" S  J\" m
   
9. 从7到3距离45& B9 n* i) a. o% u) L% G4 `4 q
   
10. 最后生成完一整棵树
    ) u. C2 V: ^% S: N# o6 K- l

复制代码