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

2744557306

实际问题引入
1 H. v' R+ g6 Q7 H4 H. J! B, @5 ]
实这道题的答案，其实就是找到这个图的最小生成树。

Kruskal算法
9 I; }! X% q; O* u4 K7 I1 K4 \此算法可以称为“加边法”，初始最小生成树的边数为 0，每迭代一次就选择一条满足条件的最小代价的边，加入到最小生成树边的集合里面。
其实核心思想就是贪心思想：通过局部最优达到整体最优

# f& B6 s8 p1 F. p; a# F0 z将所有的边权进行排序
2 F0 i" P6 _9 [. t2 K不断迭代选择权最小的边，直到所有的点被连起来（边数=节点数-1）。
在迭代期间，如果边构成了环，就要丢弃该边，因为树中是不存在环的！
) m: V  k& L. A: Y( i整体代码展示
在matlab中，最小生成树的生成直接用minspantree()函数就行。

1. s=[1,1,1,1,2,2,3,3,4,4,5,5,6];
   5 ^! r  V0 f3 c- Y7 _
2. t=[2,3,4,5,3,6,5,7,5,6,6,7,7];, b; o, E; X% x5 C  F2 X
   
3. w=[35,24,10,25,25,20,15,11,12,30,15,25,18];
   $ b7 n2 S\" S2 t+ w2 K8 _' i2 g
4. names={'1','2','3','4','5','6','7'};
   . U$ G  g, Y& T2 g& h$ L' S
5. G=graph(s,t,w,names);
   / H. e% ^& m+ @/ e
6. p=plot(G,"EdgeLabel",G.Edges.Weight);, B  p- N8 e# J) ?5 S3 G% _
   
7. % 求解最小生成树
   $ v/ W4 u: r, N5 S, g
8. T=minspantree(G,"Method","sparse");\" ]\" O+ V# s* t
   
9. % sparse代表的是Kruskal算法
   6 a. }0 m3 T2 c4 `
10. % dense代表的是Prim算法
    8 w; u; }\" V- s8 a
11. # S2 R+ _5 C' i8 U; W, i( Z
    
12. % sparse:Kruskal算法
    # m9 x& a; X2 Y) q- D
13. % 算法按权重对所有的边排序，然后将不构成循环的边添加到树中
    $ Y, o% M2 j# `5 f6 b8 E8 M
14. p=plot(G,"EdgeLabel",G.Edges.Weight);
    ) X6 l) D' G3 K8 Y' N
15. highlight(p,T,"NodeColor","red","EdgeColor","red");   l$ n. E. Y  ?
    
16. % 将最小生成树的边设置为红色!
    2 Q2 t# p. L, \4 M! F$ M  T

复制代码

, ]! g! ]- r0 Y' q6 ?/ p生成的最小生成树：
; |, T* E/ R+ M  m* u: x
8 [0 p3 |: Y" P: z4 V我们也可以把最小生成树的边和节点打印出来，也可以把整段路的权加起来看看：
, Q, X! f' e& o, |8 L尾声

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

& d7 X; Y) b9 d: _& l- C! l
' E! M2 [: V6 Z7 E+ P, ~( }