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

2744557306

实际问题引入
; c9 |3 Y3 A0 z
实这道题的答案，其实就是找到这个图的最小生成树。
6 b1 V' k% H4 B* G* P' G- r
Kruskal算法
此算法可以称为“加边法”，初始最小生成树的边数为 0，每迭代一次就选择一条满足条件的最小代价的边，加入到最小生成树边的集合里面。
其实核心思想就是贪心思想：通过局部最优达到整体最优

将所有的边权进行排序
不断迭代选择权最小的边，直到所有的点被连起来（边数=节点数-1）。
/ z" _7 S9 k6 B7 d# Z在迭代期间，如果边构成了环，就要丢弃该边，因为树中是不存在环的！
/ q1 c. T8 m& S6 {* n* t) U- j整体代码展示
在matlab中，最小生成树的生成直接用minspantree()函数就行。

1. s=[1,1,1,1,2,2,3,3,4,4,5,5,6];( o. O' ]! P3 G
   
2. t=[2,3,4,5,3,6,5,7,5,6,6,7,7];
   0 B- r* A2 a7 J
3. w=[35,24,10,25,25,20,15,11,12,30,15,25,18];
   / C% p2 d9 K. c
4. names={'1','2','3','4','5','6','7'};$ ?+ ?2 a9 {5 P0 j9 {* y
   
5. G=graph(s,t,w,names);
   , O, O% ^4 w; k0 X& z
6. p=plot(G,"EdgeLabel",G.Edges.Weight);* P% G) c3 \' `1 l3 u1 j
   
7. % 求解最小生成树
   ) h* {& e- P8 l9 B3 t# L- f
8. T=minspantree(G,"Method","sparse");
   ! X$ w/ M6 k/ w  h
9. % sparse代表的是Kruskal算法
   ! Z( k$ P! k+ i; t
10. % dense代表的是Prim算法2 Q9 B, C! a- L. X3 B, N
    
11. 
    5 @8 C# X* {& R. [\" c
12. % sparse:Kruskal算法
    , [) o& i; i( D. e4 ]' W) r
13. % 算法按权重对所有的边排序，然后将不构成循环的边添加到树中
    # @  F2 C' P$ i3 B3 B: \
14. p=plot(G,"EdgeLabel",G.Edges.Weight);
    % [6 }. s$ ]! n& ]: r# h
15. highlight(p,T,"NodeColor","red","EdgeColor","red");
    \" }, `3 D5 ]$ g8 x% H$ m6 L9 u4 C
16. % 将最小生成树的边设置为红色!4 _  R% n! T' ?1 s4 P$ c4 E0 `1 J
    

复制代码

) I/ Z) ^( L! G. z5 w2 t
生成的最小生成树：

我们也可以把最小生成树的边和节点打印出来，也可以把整段路的权加起来看看：
* R7 z5 a2 N0 p7 O# Y尾声

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

( O5 j) [1 H, E