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

2744557306

实际问题引入

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

Kruskal算法
此算法可以称为“加边法”，初始最小生成树的边数为 0，每迭代一次就选择一条满足条件的最小代价的边，加入到最小生成树边的集合里面。
2 _6 k; T( R  e$ D# }& u其实核心思想就是贪心思想：通过局部最优达到整体最优
3 e( r) o5 _, h# R
将所有的边权进行排序
; `* u+ @1 [( Y$ }' _  D  Q8 T不断迭代选择权最小的边，直到所有的点被连起来（边数=节点数-1）。
' A1 v8 h6 @, ]- e在迭代期间，如果边构成了环，就要丢弃该边，因为树中是不存在环的！
% m. u& q6 T! ?7 \2 r整体代码展示
在matlab中，最小生成树的生成直接用minspantree()函数就行。

1. s=[1,1,1,1,2,2,3,3,4,4,5,5,6];& c8 O# B( B2 h  Y& E5 U
   
2. t=[2,3,4,5,3,6,5,7,5,6,6,7,7];& z7 N/ W8 v& o  ?# {+ A% d
   
3. w=[35,24,10,25,25,20,15,11,12,30,15,25,18];& a% ]0 R. i* |\" \2 G
   
4. names={'1','2','3','4','5','6','7'};
   . d8 Y- H2 o+ d9 y
5. G=graph(s,t,w,names);
   ( G( H( u2 q0 Z0 w5 |3 W
6. p=plot(G,"EdgeLabel",G.Edges.Weight);- _7 ?$ ~7 _1 p$ C9 o
   
7. % 求解最小生成树
   \" O& t4 Q$ \2 _. d
8. T=minspantree(G,"Method","sparse");
   ; @* z3 d4 ~) p: E0 A
9. % sparse代表的是Kruskal算法
   % T! N8 D# N) `3 V( Y
10. % dense代表的是Prim算法
    5 `2 }& Y/ D1 ?
11. 6 ~0 D/ ^8 M- g$ w- i3 L
    
12. % sparse:Kruskal算法+ N0 _# b* Z\" a; Y/ ?
    
13. % 算法按权重对所有的边排序，然后将不构成循环的边添加到树中) ?( z' k0 B* i* K, z
    
14. p=plot(G,"EdgeLabel",G.Edges.Weight);
    8 G  I' c  r/ F; a
15. highlight(p,T,"NodeColor","red","EdgeColor","red"); 1 e# z9 p, ~# }; L) d- k6 K
    
16. % 将最小生成树的边设置为红色!
    9 T5 M5 _# r. U$ P

复制代码

& N$ ?, n/ D- s. X
( q9 J* e0 n' Q( k3 |& H生成的最小生成树：

我们也可以把最小生成树的边和节点打印出来，也可以把整段路的权加起来看看：
5 t% O. T, P6 A' a1 Y尾声

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