【图论】【Matlab】最小生成树之Kruskal算法【贪心思想超详细详解Kruskal算法并应用】

2744557306

实际问题引入
' S) Z" M- J, z3 b- a
( l/ F, W2 l+ H* r" e实这道题的答案，其实就是找到这个图的最小生成树。

# y9 y& p* Z/ w( s* P9 h/ w6 q( H' UKruskal算法
此算法可以称为“加边法”，初始最小生成树的边数为 0，每迭代一次就选择一条满足条件的最小代价的边，加入到最小生成树边的集合里面。
其实核心思想就是贪心思想：通过局部最优达到整体最优
+ l5 L! o' d4 S: B
, A1 G- Y4 q0 p" S将所有的边权进行排序
不断迭代选择权最小的边，直到所有的点被连起来（边数=节点数-1）。
& f: t! C+ |  {3 |( q* g在迭代期间，如果边构成了环，就要丢弃该边，因为树中是不存在环的！
整体代码展示
在matlab中，最小生成树的生成直接用minspantree()函数就行。

1. s=[1,1,1,1,2,2,3,3,4,4,5,5,6];
   $ Z  v8 S2 o2 V9 d
2. t=[2,3,4,5,3,6,5,7,5,6,6,7,7];
   ! N. b# P) s  g6 [, P. l4 Y7 r
3. w=[35,24,10,25,25,20,15,11,12,30,15,25,18];
   \" v$ y7 @! k; O4 d3 U, _3 y( ?+ t
4. names={'1','2','3','4','5','6','7'};
   7 z+ G0 I! R; f6 S; w  T
5. G=graph(s,t,w,names);
   % s9 q3 |$ e$ i. w* `- N+ g) K
6. p=plot(G,"EdgeLabel",G.Edges.Weight);
   & Q$ E4 b\" B5 A1 ]4 z+ i% H
7. % 求解最小生成树8 X/ S8 W* `, s0 w1 Z
   
8. T=minspantree(G,"Method","sparse");7 W* c8 K$ e5 v( w. ]) n7 X1 K
   
9. % sparse代表的是Kruskal算法: C* x; S7 \# G% f
   
10. % dense代表的是Prim算法
    ' _5 Z% M/ P! t6 ?1 S0 G9 \
11. 9 Q4 C: x- _/ f
    
12. % sparse:Kruskal算法
    \" t2 K9 s- ?) }( e
13. % 算法按权重对所有的边排序，然后将不构成循环的边添加到树中: r  p/ |& s( v! P% M/ C. x- X\" c
    
14. p=plot(G,"EdgeLabel",G.Edges.Weight);! Q( K& W7 y' _3 |& Y7 u- ^
    
15. highlight(p,T,"NodeColor","red","EdgeColor","red"); 0 |/ G4 e! X2 a4 Z
    
16. % 将最小生成树的边设置为红色!
    ) b/ h2 Q! x2 o- ]8 w+ ~

复制代码

' B2 m7 P% W# |+ e- B% j
9 g) [. I3 q! e6 t0 M生成的最小生成树：

我们也可以把最小生成树的边和节点打印出来，也可以把整段路的权加起来看看：
( _8 [# s- v) O2 G" v. b尾声

看到这里，相信我们已经学会Kruskal算法寻找最小生成树的过程了，当然，这离数学建模的要求，离我们的目标还非常遥远，博主在不断学习的过程中，也希望可以通过分享学习日记的方式带动大家！

+ `- D% h2 W* t& ^9 D) L% u
; Q3 p' G2 p' A) u/ K+ V