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

2744557306

实际问题引入

实这道题的答案，其实就是找到这个图的最小生成树。
6 [9 e" s. j& K, H
Kruskal算法
此算法可以称为“加边法”，初始最小生成树的边数为 0，每迭代一次就选择一条满足条件的最小代价的边，加入到最小生成树边的集合里面。
$ A, m( ~' u1 ]; `/ E  [8 F其实核心思想就是贪心思想：通过局部最优达到整体最优
8 j/ i- s6 P6 j" h9 i$ a. h
3 S7 _/ J6 N8 R5 T: R' U  M将所有的边权进行排序
不断迭代选择权最小的边，直到所有的点被连起来（边数=节点数-1）。
在迭代期间，如果边构成了环，就要丢弃该边，因为树中是不存在环的！
" s, S' `* I. f9 B  y4 w整体代码展示
在matlab中，最小生成树的生成直接用minspantree()函数就行。

1. s=[1,1,1,1,2,2,3,3,4,4,5,5,6];
   - r3 j  i6 `* `0 L+ ]
2. t=[2,3,4,5,3,6,5,7,5,6,6,7,7];
   ; [, v4 ?1 l& S
3. w=[35,24,10,25,25,20,15,11,12,30,15,25,18];% K' ?, T2 A5 b
   
4. names={'1','2','3','4','5','6','7'};6 ~5 A# L3 |2 R% R' J\" v' h
   
5. G=graph(s,t,w,names);
   6 u2 l7 h4 U4 {\" V1 }
6. p=plot(G,"EdgeLabel",G.Edges.Weight);% ^5 v$ Z2 J' N2 e5 D( e
   
7. % 求解最小生成树
   ; h. c, v! t9 H- m- a  ?. O
8. T=minspantree(G,"Method","sparse");3 z0 Y# m; P# z' Q2 |
   
9. % sparse代表的是Kruskal算法$ G) ~$ f: ]1 D' k0 f0 E
   
10. % dense代表的是Prim算法5 L* B) O7 r% @1 d# @4 f: w. V
    
11. 
    ) G- f& `- f: m& w4 m& o2 b
12. % sparse:Kruskal算法* s' U4 o- }7 ], ^\" ^- v. X\" N. c
    
13. % 算法按权重对所有的边排序，然后将不构成循环的边添加到树中
      z# j. S9 |- `4 u4 ~( b: a
14. p=plot(G,"EdgeLabel",G.Edges.Weight);+ Q1 j5 f+ c& e) q
    
15. highlight(p,T,"NodeColor","red","EdgeColor","red"); 3 E' E8 n3 M- T  I- N8 m2 `; g+ g
    
16. % 将最小生成树的边设置为红色!# v\" l4 f/ Z9 o/ H7 T
    

复制代码

生成的最小生成树：
" i( Z8 x1 S6 s2 F7 r& ~; n
我们也可以把最小生成树的边和节点打印出来，也可以把整段路的权加起来看看：
! E0 U1 u9 s7 V9 e5 N, J尾声

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

+ Y7 j6 i' w/ D6 U4 V: V6 W
! f* Y, {/ q9 |! z+ p# b. S$ h