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

2744557306

实际问题引入
0 }4 V4 n/ ^0 {/ ]3 x/ a
4 J. a6 o( C" o" h实这道题的答案，其实就是找到这个图的最小生成树。
3 h; I1 q: n' A! W7 O* i
- x) }. Q; `: m8 p7 z7 BKruskal算法
此算法可以称为“加边法”，初始最小生成树的边数为 0，每迭代一次就选择一条满足条件的最小代价的边，加入到最小生成树边的集合里面。
8 ~0 T3 p3 }2 f, ?/ z6 H" c其实核心思想就是贪心思想：通过局部最优达到整体最优

. k7 D! C! n' F! T. N5 {将所有的边权进行排序
* f3 U7 W! Y) e& w) ^1 N  o不断迭代选择权最小的边，直到所有的点被连起来（边数=节点数-1）。
在迭代期间，如果边构成了环，就要丢弃该边，因为树中是不存在环的！
% }+ n) ^+ s) p9 ^9 G7 c# ]整体代码展示
在matlab中，最小生成树的生成直接用minspantree()函数就行。

1. s=[1,1,1,1,2,2,3,3,4,4,5,5,6];
   \" T2 n6 o+ `5 k3 L- }2 M* y( ~1 u9 \5 a
2. t=[2,3,4,5,3,6,5,7,5,6,6,7,7];
     y. H% w& N3 x- q
3. w=[35,24,10,25,25,20,15,11,12,30,15,25,18];
   $ W7 g$ a3 g( Q\" B3 |) }0 S
4. names={'1','2','3','4','5','6','7'};1 H( h, U6 i6 l% d& t
   
5. G=graph(s,t,w,names);/ i4 r3 x5 k9 C$ _/ z7 j
   
6. p=plot(G,"EdgeLabel",G.Edges.Weight);6 u, c) C3 l3 \( @7 Y
   
7. % 求解最小生成树3 s7 P/ o2 H6 T% o8 d) h) B6 E6 r
   
8. T=minspantree(G,"Method","sparse");7 k8 u+ _8 L& S- n$ M, N8 T% q& y+ |
   
9. % sparse代表的是Kruskal算法3 t\" \0 j/ ~, H
   
10. % dense代表的是Prim算法, k# z+ {% j4 j9 z
    
11. - U# s0 A\" }( H0 X$ Z0 Y
    
12. % sparse:Kruskal算法0 S$ _) Y& r\" q1 _6 k
    
13. % 算法按权重对所有的边排序，然后将不构成循环的边添加到树中+ ]! X3 o( \\" t6 D7 E: i
    
14. p=plot(G,"EdgeLabel",G.Edges.Weight);( l! n# p1 r4 i& V) j
    
15. highlight(p,T,"NodeColor","red","EdgeColor","red");
    . |6 }) E* Z, W$ Z/ T
16. % 将最小生成树的边设置为红色!: h7 W5 a9 p8 ?- z# y' ~/ D3 f
    

复制代码

$ p4 Q  p: ^+ }! z. {: V2 O
5 Z4 p6 o; ]9 ?; z: W% }6 `7 c- s" a生成的最小生成树：
* o  d! j+ W  ]. i& h- T# j" G
' }* P; E4 m$ X+ ?6 H我们也可以把最小生成树的边和节点打印出来，也可以把整段路的权加起来看看：
尾声

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

$ d, N1 s8 O/ T. L( J* l. r