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

2744557306

实际问题引入
5 Z2 e2 t  X) d
实这道题的答案，其实就是找到这个图的最小生成树。

6 b5 v; S. {3 ]% ^( @4 d3 ], P. X1 r. JKruskal算法
此算法可以称为“加边法”，初始最小生成树的边数为 0，每迭代一次就选择一条满足条件的最小代价的边，加入到最小生成树边的集合里面。
其实核心思想就是贪心思想：通过局部最优达到整体最优

8 j* k- o# \1 v2 l6 @将所有的边权进行排序
不断迭代选择权最小的边，直到所有的点被连起来（边数=节点数-1）。
在迭代期间，如果边构成了环，就要丢弃该边，因为树中是不存在环的！
整体代码展示
在matlab中，最小生成树的生成直接用minspantree()函数就行。

1. s=[1,1,1,1,2,2,3,3,4,4,5,5,6];
   / {, \8 t9 ?% a
2. t=[2,3,4,5,3,6,5,7,5,6,6,7,7];' X3 ]' `0 G: W2 C; t. i
   
3. w=[35,24,10,25,25,20,15,11,12,30,15,25,18];
   1 Q: y1 O- f7 L, ?: K
4. names={'1','2','3','4','5','6','7'};* B\" X) \\" r, s
   
5. G=graph(s,t,w,names);
   6 H# V# I7 O' W4 ~
6. p=plot(G,"EdgeLabel",G.Edges.Weight);
   5 @/ t7 Q$ ?5 \' h- f) w* S
7. % 求解最小生成树  z4 m\" c- b  O
   
8. T=minspantree(G,"Method","sparse");
   1 m( t) q4 `+ \4 P4 P
9. % sparse代表的是Kruskal算法$ P; o+ h5 g6 w  K1 J
   
10. % dense代表的是Prim算法2 y* b6 Z7 {- p' |4 H* A* t( X
    
11. 4 l$ f& E4 g' Y% z( w4 d
    
12. % sparse:Kruskal算法
    8 w4 s& J) Z2 w6 g- a  G+ i
13. % 算法按权重对所有的边排序，然后将不构成循环的边添加到树中# B! `4 T3 u2 A
    
14. p=plot(G,"EdgeLabel",G.Edges.Weight);
    2 {9 \+ Z6 d9 k& i+ V  Y
15. highlight(p,T,"NodeColor","red","EdgeColor","red"); . i  \6 k; q  h) U
    
16. % 将最小生成树的边设置为红色!- s  z' v6 @$ G7 A% n% `
    

复制代码

3 z8 A5 g6 V1 O! A
; g/ m9 X7 q( @' y' h9 v生成的最小生成树：

! v4 O- a2 k  L  d2 t9 V! X我们也可以把最小生成树的边和节点打印出来，也可以把整段路的权加起来看看：
尾声

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