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

2744557306

实际问题引入

实这道题的答案，其实就是找到这个图的最小生成树。
! x2 a5 H8 s3 U3 c
, h2 P; k& w5 o  Z* hKruskal算法
此算法可以称为“加边法”，初始最小生成树的边数为 0，每迭代一次就选择一条满足条件的最小代价的边，加入到最小生成树边的集合里面。
其实核心思想就是贪心思想：通过局部最优达到整体最优
$ E# W' H& V! B5 S
% \3 L0 @2 ]) `6 k将所有的边权进行排序
不断迭代选择权最小的边，直到所有的点被连起来（边数=节点数-1）。
: p- s, F+ e% M+ @在迭代期间，如果边构成了环，就要丢弃该边，因为树中是不存在环的！
整体代码展示
在matlab中，最小生成树的生成直接用minspantree()函数就行。

1. s=[1,1,1,1,2,2,3,3,4,4,5,5,6];+ g1 \3 S$ \# T\" Z; R5 _
   
2. t=[2,3,4,5,3,6,5,7,5,6,6,7,7];
   % K( m9 B2 f# ^- F# E* p
3. w=[35,24,10,25,25,20,15,11,12,30,15,25,18];
   * F4 Y. Q6 H# Z% B1 E\" a
4. names={'1','2','3','4','5','6','7'};8 e0 x, H' X' b% C3 U
   
5. G=graph(s,t,w,names);
   6 T* m6 w, y* N0 a
6. p=plot(G,"EdgeLabel",G.Edges.Weight);
   ) i; ^, o3 r+ m1 U6 R* G
7. % 求解最小生成树9 Q/ Z& I1 v3 H; v
   
8. T=minspantree(G,"Method","sparse");# t' u/ S! y% H8 p! v
   
9. % sparse代表的是Kruskal算法
   * D. Z0 `  s\" G5 L9 a
10. % dense代表的是Prim算法
    7 W  J/ q7 W' E& `  F: S2 r* [
11. , R4 f\" M/ D- V9 H
    
12. % sparse:Kruskal算法8 ~+ i% _& L5 Q6 y  U; A
    
13. % 算法按权重对所有的边排序，然后将不构成循环的边添加到树中
    ) [( X* D8 s% Y  Q, ^1 a
14. p=plot(G,"EdgeLabel",G.Edges.Weight);+ J0 O8 E9 ]2 a+ G
    
15. highlight(p,T,"NodeColor","red","EdgeColor","red");
    ( V; Z: U8 t2 Q) b2 h
16. % 将最小生成树的边设置为红色!) Y7 p6 L# p7 t! }
    

复制代码

$ ^1 {4 |" H8 E  b- y' B& {
生成的最小生成树：
" Z& [  e) ^: m" w3 H
我们也可以把最小生成树的边和节点打印出来，也可以把整段路的权加起来看看：
尾声

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