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

2744557306

实际问题引入
# @+ w% p8 X# A* w6 f
0 q; ]8 g: ~6 a6 e0 W5 j$ O! m实这道题的答案，其实就是找到这个图的最小生成树。

9 C9 y7 t7 R8 s3 T5 PKruskal算法
- d2 i; @# ^/ c此算法可以称为“加边法”，初始最小生成树的边数为 0，每迭代一次就选择一条满足条件的最小代价的边，加入到最小生成树边的集合里面。
其实核心思想就是贪心思想：通过局部最优达到整体最优
% I: _5 [: T. {
6 G) \6 e  s& p将所有的边权进行排序
8 j6 F8 T+ [4 o4 C- c5 O# l- b不断迭代选择权最小的边，直到所有的点被连起来（边数=节点数-1）。
在迭代期间，如果边构成了环，就要丢弃该边，因为树中是不存在环的！
整体代码展示
3 S9 u% y' a; H' D# l, P% @# L2 P在matlab中，最小生成树的生成直接用minspantree()函数就行。

1. s=[1,1,1,1,2,2,3,3,4,4,5,5,6];- G4 h  D6 C* d% c3 u
   
2. t=[2,3,4,5,3,6,5,7,5,6,6,7,7];
   - N1 ~# x7 G: z* o$ p2 N; w
3. w=[35,24,10,25,25,20,15,11,12,30,15,25,18];
   8 a, _7 y& l; r# Z# {! I: i\" w
4. names={'1','2','3','4','5','6','7'};
   0 G# n$ ]& T. B
5. G=graph(s,t,w,names);6 E% S) P' F) `' I! S$ p, G# A6 U
   
6. p=plot(G,"EdgeLabel",G.Edges.Weight);$ ^: w; m( H; Q9 Q* ?\" V2 z7 z
   
7. % 求解最小生成树
   7 h# N, J/ l9 T, O; i6 {
8. T=minspantree(G,"Method","sparse");
   5 {* W$ r: z6 _% x
9. % sparse代表的是Kruskal算法
   ( P, F% C& f7 a7 Y0 V' q& [- T
10. % dense代表的是Prim算法
    ) N\" f$ l) P. E. h( c6 \' i# y5 f
11.   X; a4 ~0 F# v) b0 ?- P2 e' c
    
12. % sparse:Kruskal算法% P7 r2 C/ z\" P
    
13. % 算法按权重对所有的边排序，然后将不构成循环的边添加到树中
    9 h; v# l; W3 f0 A
14. p=plot(G,"EdgeLabel",G.Edges.Weight);9 _* C2 b' j! U5 a
    
15. highlight(p,T,"NodeColor","red","EdgeColor","red");
    ! @3 [, V2 P# _
16. % 将最小生成树的边设置为红色!
    7 T% t; q( b# n2 O

复制代码

, v6 D. y$ l$ b* s生成的最小生成树：

我们也可以把最小生成树的边和节点打印出来，也可以把整段路的权加起来看看：
尾声

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

) W$ i. N7 N. V  N0 Z5 D