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

2744557306

实际问题引入

: t6 m% P* v" [) V实这道题的答案，其实就是找到这个图的最小生成树。

Kruskal算法
" _( [$ `; e# D8 m; g5 y  C此算法可以称为“加边法”，初始最小生成树的边数为 0，每迭代一次就选择一条满足条件的最小代价的边，加入到最小生成树边的集合里面。
! \8 }. n" @5 C其实核心思想就是贪心思想：通过局部最优达到整体最优

( o! M, @' D7 j$ Q2 W1 F将所有的边权进行排序
: `: g7 Z8 w( d3 A2 s3 m) }不断迭代选择权最小的边，直到所有的点被连起来（边数=节点数-1）。
在迭代期间，如果边构成了环，就要丢弃该边，因为树中是不存在环的！
! m2 }* j' k  M整体代码展示
/ g. B4 R  @2 w) m: A# x. t+ x在matlab中，最小生成树的生成直接用minspantree()函数就行。

1. s=[1,1,1,1,2,2,3,3,4,4,5,5,6];
   ! _% P4 J, |. T* [( F+ n& E
2. t=[2,3,4,5,3,6,5,7,5,6,6,7,7];: S1 {6 s% D+ z* j* E  h5 {
   
3. w=[35,24,10,25,25,20,15,11,12,30,15,25,18];6 {4 _\" G' Z0 H' r: s! c* C
   
4. names={'1','2','3','4','5','6','7'};, E0 K\" d! J. {6 h2 u6 D, ?\" |% F\" T8 J
   
5. G=graph(s,t,w,names);
   - Q\" L6 K# Z6 ]: I; F* t
6. p=plot(G,"EdgeLabel",G.Edges.Weight);
   \" J! y8 x7 O# M5 j9 ]
7. % 求解最小生成树\" R- t8 m: t, x9 V3 U. ^1 D$ z  x4 Y
   
8. T=minspantree(G,"Method","sparse");
   2 `: O8 r5 x7 _& B$ {6 Z3 Z- i' @
9. % sparse代表的是Kruskal算法
   9 H- L6 y+ E% D) E9 G
10. % dense代表的是Prim算法
      t5 C+ i* T& L, N- f5 S1 H* o2 I( o
11. 5 P3 \7 O0 s& p* K; d5 ^* b- |' D
    
12. % sparse:Kruskal算法
    ( d$ ^7 o/ {  p\" {  s, R
13. % 算法按权重对所有的边排序，然后将不构成循环的边添加到树中( z4 }7 q2 g8 T( U& p0 |# K1 ]
    
14. p=plot(G,"EdgeLabel",G.Edges.Weight);5 I5 w* D  B2 s\" a% h
    
15. highlight(p,T,"NodeColor","red","EdgeColor","red");
    1 N7 V% J# g\" O$ e7 Y
16. % 将最小生成树的边设置为红色!1 M# m2 `2 N* w: H/ x
    

复制代码

8 u/ {; U0 j& F' D生成的最小生成树：

我们也可以把最小生成树的边和节点打印出来，也可以把整段路的权加起来看看：
( p& @: y9 q( G9 j1 ], H& C! H, n9 Q尾声

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

6 X( ]. d- }  Q