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

2744557306

实际问题引入

实这道题的答案，其实就是找到这个图的最小生成树。
4 \- |5 i, p( q
Kruskal算法
8 Z0 T. j3 t9 d7 C  p此算法可以称为“加边法”，初始最小生成树的边数为 0，每迭代一次就选择一条满足条件的最小代价的边，加入到最小生成树边的集合里面。
其实核心思想就是贪心思想：通过局部最优达到整体最优
9 W) D2 E( p- r" d! B- z1 j4 q
) v0 C3 ?( y) N) ~5 N* s& ]6 ?. ^将所有的边权进行排序
不断迭代选择权最小的边，直到所有的点被连起来（边数=节点数-1）。
3 ~" A" b. @& }5 U在迭代期间，如果边构成了环，就要丢弃该边，因为树中是不存在环的！
+ T. E7 H& F+ f& d整体代码展示
在matlab中，最小生成树的生成直接用minspantree()函数就行。

1. s=[1,1,1,1,2,2,3,3,4,4,5,5,6];1 o7 g! g3 R& V8 G
   
2. t=[2,3,4,5,3,6,5,7,5,6,6,7,7];
   4 M' c$ B5 W8 j: W; n. J* V
3. w=[35,24,10,25,25,20,15,11,12,30,15,25,18];0 ^4 v8 V4 D. ]1 M) A% Y
   
4. names={'1','2','3','4','5','6','7'};0 s; h$ G- }& i# p) r
   
5. G=graph(s,t,w,names);- k: s6 U4 e' B2 K- P' X  Z
   
6. p=plot(G,"EdgeLabel",G.Edges.Weight);% W- Q  D% D0 p; T: E
   
7. % 求解最小生成树
   # K  g' V! E  b. j, ]6 S
8. T=minspantree(G,"Method","sparse");6 j\" w; A, n8 y5 X7 _  S* z
   
9. % sparse代表的是Kruskal算法- z2 k. I5 U* _+ u; X) [9 v; {% o
   
10. % dense代表的是Prim算法
    6 \$ i\" Y$ h4 j
11. 
    . J1 K9 K2 k  W: h
12. % sparse:Kruskal算法' [; q. E# v+ e
    
13. % 算法按权重对所有的边排序，然后将不构成循环的边添加到树中
    / G+ n+ w4 q& }: p3 Q; w
14. p=plot(G,"EdgeLabel",G.Edges.Weight);& f4 K& m* U( D6 e/ i
    
15. highlight(p,T,"NodeColor","red","EdgeColor","red"); 9 N& F7 I  o+ ^& W6 i, N
    
16. % 将最小生成树的边设置为红色!
    , S& i7 U* K; D+ w) W

复制代码

  S  E$ E) r0 k4 @9 H( ^/ U. A生成的最小生成树：
- v, l+ w7 N. i/ d! q; |
我们也可以把最小生成树的边和节点打印出来，也可以把整段路的权加起来看看：
3 M! W* M# [3 y5 J. H尾声

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

: {# b8 N) Q- G) K+ y- }