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

2744557306

实际问题引入

实这道题的答案，其实就是找到这个图的最小生成树。
4 V" J1 g; `  u" S$ S- a
' `9 f3 O' j& V7 _& y* [% h1 u* CKruskal算法
此算法可以称为“加边法”，初始最小生成树的边数为 0，每迭代一次就选择一条满足条件的最小代价的边，加入到最小生成树边的集合里面。
其实核心思想就是贪心思想：通过局部最优达到整体最优

将所有的边权进行排序
( d% O6 s) |" a: ?9 f) ]不断迭代选择权最小的边，直到所有的点被连起来（边数=节点数-1）。
在迭代期间，如果边构成了环，就要丢弃该边，因为树中是不存在环的！
7 {& L( t% ~1 ]0 Y- M整体代码展示
7 `( I& {; w* z7 X2 a在matlab中，最小生成树的生成直接用minspantree()函数就行。

1. s=[1,1,1,1,2,2,3,3,4,4,5,5,6];
   1 n! F' P9 |& I6 j. y
2. t=[2,3,4,5,3,6,5,7,5,6,6,7,7];
   # C7 k5 s; A9 h, f' ?3 S4 c, M
3. w=[35,24,10,25,25,20,15,11,12,30,15,25,18];
   5 G5 L$ p+ J* n9 H\" U0 @
4. names={'1','2','3','4','5','6','7'};' B0 L  d  o; \+ J
   
5. G=graph(s,t,w,names);
   \" @\" v\" K( C0 G% [' M# M5 H
6. p=plot(G,"EdgeLabel",G.Edges.Weight);( \\" T2 f1 d$ `& X4 Q2 l# _
   
7. % 求解最小生成树
   + W5 }& P, X. s
8. T=minspantree(G,"Method","sparse");! r6 T' q) B  P' f1 a; Q
   
9. % sparse代表的是Kruskal算法) {4 [# G* `* N; C4 e0 z; A
   
10. % dense代表的是Prim算法. Z: ^! o# O! T! W& L
    
11. , J8 K2 L3 l7 G, ]% X% E9 |
    
12. % sparse:Kruskal算法8 |$ [8 \1 v$ k/ V0 _2 \
    
13. % 算法按权重对所有的边排序，然后将不构成循环的边添加到树中; D1 }% ?/ I; r( h! {
    
14. p=plot(G,"EdgeLabel",G.Edges.Weight);
    * K4 M: `9 Y; |# ?% R0 ]7 m
15. highlight(p,T,"NodeColor","red","EdgeColor","red");
    ( C, ]/ i2 G' l# K
16. % 将最小生成树的边设置为红色!- Q: Z' E' K4 P
    

复制代码

  ]: o1 ~6 |+ z% j" h生成的最小生成树：

我们也可以把最小生成树的边和节点打印出来，也可以把整段路的权加起来看看：
尾声

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

8 Z) g7 C9 c" X" G) s, C