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

2744557306

实际问题引入

实这道题的答案，其实就是找到这个图的最小生成树。

Kruskal算法
此算法可以称为“加边法”，初始最小生成树的边数为 0，每迭代一次就选择一条满足条件的最小代价的边，加入到最小生成树边的集合里面。
% w2 f5 p/ d5 k8 |4 X其实核心思想就是贪心思想：通过局部最优达到整体最优

将所有的边权进行排序
5 f3 J7 ~% {7 h$ ^3 j不断迭代选择权最小的边，直到所有的点被连起来（边数=节点数-1）。
+ x. B# D0 |; l7 [. F在迭代期间，如果边构成了环，就要丢弃该边，因为树中是不存在环的！
整体代码展示
9 Y- {. m" ^* P& L) \6 N在matlab中，最小生成树的生成直接用minspantree()函数就行。

1. s=[1,1,1,1,2,2,3,3,4,4,5,5,6];$ [6 E2 S- r4 [
   
2. t=[2,3,4,5,3,6,5,7,5,6,6,7,7];- p# j# U3 I% ]! P0 I6 {) |# _1 t
   
3. w=[35,24,10,25,25,20,15,11,12,30,15,25,18];
   8 z7 y\" H$ \( k# M- n$ P: S6 d
4. names={'1','2','3','4','5','6','7'};) K8 ]' h\" J: i7 j/ q$ G' P6 p
   
5. G=graph(s,t,w,names);
   ' J7 G; Y; i- z& `* t+ M2 H7 _
6. p=plot(G,"EdgeLabel",G.Edges.Weight);
   2 g7 E. G* Q\" O6 F6 p
7. % 求解最小生成树- n1 u6 L  Y4 q/ j. E
   
8. T=minspantree(G,"Method","sparse");
   + O1 c! q4 X+ m& E. m
9. % sparse代表的是Kruskal算法
   3 h$ h7 w4 R. ]+ n2 v
10. % dense代表的是Prim算法
    , n( T9 q: I  w
11. % ]/ q4 e2 ]. D: S) j' ]1 i! _$ N
    
12. % sparse:Kruskal算法
    \" E9 t& n# D* ?( k5 }) _
13. % 算法按权重对所有的边排序，然后将不构成循环的边添加到树中8 X) {1 A, g3 f) N: ~2 ^0 R
    
14. p=plot(G,"EdgeLabel",G.Edges.Weight);
    ; d. F* A$ u% b
15. highlight(p,T,"NodeColor","red","EdgeColor","red");
    6 W# u2 d9 W8 C5 ]
16. % 将最小生成树的边设置为红色!. u; u7 ^* q8 L6 k
    

复制代码

' }: Z: g8 T; q5 {
: J3 I& |( D8 C* Y& v生成的最小生成树：
9 J, ?* c' D, y, J4 d
  |8 K/ Q; }* z6 G* e# |9 H我们也可以把最小生成树的边和节点打印出来，也可以把整段路的权加起来看看：
尾声

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

% ^- D4 J) b% _
8 r4 h2 ]/ z9 d! [9 Y  a