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

2744557306

实际问题引入
# @  b" S: w7 D3 i$ |" m
- I" q8 j5 \- T3 w3 E实这道题的答案，其实就是找到这个图的最小生成树。

Kruskal算法
3 A; X! R& t( z# p' y! m# s5 g此算法可以称为“加边法”，初始最小生成树的边数为 0，每迭代一次就选择一条满足条件的最小代价的边，加入到最小生成树边的集合里面。
; u* x- H2 M0 a+ d4 k0 [1 m9 K其实核心思想就是贪心思想：通过局部最优达到整体最优
, e/ S, K9 [! \( v
+ [& J' ?; y6 K, Q& Q8 m将所有的边权进行排序
不断迭代选择权最小的边，直到所有的点被连起来（边数=节点数-1）。
在迭代期间，如果边构成了环，就要丢弃该边，因为树中是不存在环的！
整体代码展示
在matlab中，最小生成树的生成直接用minspantree()函数就行。

1. s=[1,1,1,1,2,2,3,3,4,4,5,5,6];
   $ p! L\" U0 c: q' w2 K. x
2. t=[2,3,4,5,3,6,5,7,5,6,6,7,7];  I& Y' i  a\" S( \4 _8 w. `
   
3. w=[35,24,10,25,25,20,15,11,12,30,15,25,18];
   \" \7 C. W5 z9 X( M9 C6 r. k: @
4. names={'1','2','3','4','5','6','7'};
   : B3 Y! y# }* n- w8 ~/ T6 v* _
5. G=graph(s,t,w,names);( Q$ a% E5 E6 f5 K# Y! D% w
   
6. p=plot(G,"EdgeLabel",G.Edges.Weight);
   4 A2 V2 A5 A2 ~! C0 _/ U
7. % 求解最小生成树
   $ K\" m; M% v# y( _0 h$ `2 c' P
8. T=minspantree(G,"Method","sparse");9 l\" O7 ^5 `( U2 G  l9 O
   
9. % sparse代表的是Kruskal算法
   / ], d1 }) C; M
10. % dense代表的是Prim算法
    7 [. n1 p  \  t  R# t9 v
11. 
    ; f\" D) G8 i\" O# g6 s+ I* b
12. % sparse:Kruskal算法+ q& ^: _' f$ s7 ?( s
    
13. % 算法按权重对所有的边排序，然后将不构成循环的边添加到树中9 K# G8 z' Q# w' G# }; k8 p
    
14. p=plot(G,"EdgeLabel",G.Edges.Weight);
    ( R/ L- `. s7 O2 |
15. highlight(p,T,"NodeColor","red","EdgeColor","red"); , _  B2 d7 \4 U2 j. e
    
16. % 将最小生成树的边设置为红色!
    ; G; I\" n3 ?. v& N$ b; T; N

复制代码

1 C* w- R$ Z) \生成的最小生成树：

我们也可以把最小生成树的边和节点打印出来，也可以把整段路的权加起来看看：
- s' s9 l, `9 C4 I" J. H, i尾声

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