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

2744557306

实际问题引入

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

Kruskal算法
1 ^6 B! t5 c' T5 q此算法可以称为“加边法”，初始最小生成树的边数为 0，每迭代一次就选择一条满足条件的最小代价的边，加入到最小生成树边的集合里面。
7 w  {! |! j- ?; g. O1 Z其实核心思想就是贪心思想：通过局部最优达到整体最优

将所有的边权进行排序
不断迭代选择权最小的边，直到所有的点被连起来（边数=节点数-1）。
在迭代期间，如果边构成了环，就要丢弃该边，因为树中是不存在环的！
整体代码展示
在matlab中，最小生成树的生成直接用minspantree()函数就行。

1. s=[1,1,1,1,2,2,3,3,4,4,5,5,6];/ i- T9 Z( }+ [
   
2. t=[2,3,4,5,3,6,5,7,5,6,6,7,7];
   ( ^4 o9 Y7 j7 B$ U! h
3. w=[35,24,10,25,25,20,15,11,12,30,15,25,18];
   - Q. b2 b+ M; n% [9 w
4. names={'1','2','3','4','5','6','7'};
   7 W4 q2 ~3 d* N9 X# r5 k; f
5. G=graph(s,t,w,names);\" O- G\" O4 ]/ D
   
6. p=plot(G,"EdgeLabel",G.Edges.Weight);
   - b$ E2 s! B, q5 {6 y1 A( o
7. % 求解最小生成树( N2 W* m- U7 a6 B, L
   
8. T=minspantree(G,"Method","sparse");8 R/ D0 O8 ^, P) |
   
9. % sparse代表的是Kruskal算法: m$ ^1 \5 d$ H* I( b7 Y! z
   
10. % dense代表的是Prim算法( v7 \( L/ G5 \7 o
    
11. 4 K6 |( t\" i0 X% l
    
12. % sparse:Kruskal算法8 j$ `5 q; i6 E\" h9 y! _
    
13. % 算法按权重对所有的边排序，然后将不构成循环的边添加到树中
    8 p. R\" x. Y% F- \5 e
14. p=plot(G,"EdgeLabel",G.Edges.Weight);/ n. b: ~8 z) i' j  B8 [
    
15. highlight(p,T,"NodeColor","red","EdgeColor","red"); - \# f) t7 Z9 T2 {) W/ G. B
    
16. % 将最小生成树的边设置为红色!
    1 z9 x. Z9 l* i; g& A* \# M

复制代码

生成的最小生成树：
' i/ k% E9 e$ t6 e6 w7 F8 O! d
我们也可以把最小生成树的边和节点打印出来，也可以把整段路的权加起来看看：
+ d) D& k9 s4 I2 B: |8 k尾声

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