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

2744557306

实际问题引入

0 t+ l) x; u; C' [实这道题的答案，其实就是找到这个图的最小生成树。

4 j% i5 f3 A9 G4 QKruskal算法
  m$ p+ |# d, K) ~- x1 H此算法可以称为“加边法”，初始最小生成树的边数为 0，每迭代一次就选择一条满足条件的最小代价的边，加入到最小生成树边的集合里面。
其实核心思想就是贪心思想：通过局部最优达到整体最优
( F  L7 I+ s! w. Q
5 @2 M' S: a0 `7 z将所有的边权进行排序
0 e, {+ U. A# M& g  x4 ^0 ?不断迭代选择权最小的边，直到所有的点被连起来（边数=节点数-1）。
( t% D* G4 w. b/ C! M1 n在迭代期间，如果边构成了环，就要丢弃该边，因为树中是不存在环的！
整体代码展示
6 K9 ^7 f2 `5 a' X6 C1 Q# ^在matlab中，最小生成树的生成直接用minspantree()函数就行。

1. s=[1,1,1,1,2,2,3,3,4,4,5,5,6];8 a8 ]6 c- N  g$ q$ e
   
2. t=[2,3,4,5,3,6,5,7,5,6,6,7,7];
   ) S/ J7 |, Y3 [# a) F+ Q7 _
3. w=[35,24,10,25,25,20,15,11,12,30,15,25,18];$ h( Y3 _. v2 K
   
4. names={'1','2','3','4','5','6','7'};
   9 f* Q$ @: S- e7 l# U
5. G=graph(s,t,w,names);
   ; s7 D7 D% b  C( W\" |2 H; H  A
6. p=plot(G,"EdgeLabel",G.Edges.Weight);
   1 X- F$ u5 V' y
7. % 求解最小生成树
   ( l( `! _' M  \/ L0 R\" d
8. T=minspantree(G,"Method","sparse");
     q# U$ R, ?# y+ X2 u+ r\" P  e
9. % sparse代表的是Kruskal算法' l2 L! I) O$ Q& q: J6 {2 A
   
10. % dense代表的是Prim算法) u9 j* J( x\" X, Q/ t6 T
    
11. 
    + P7 J- D0 B2 z- R' Y7 D, W
12. % sparse:Kruskal算法9 ]0 u4 A) ~; W2 Q
    
13. % 算法按权重对所有的边排序，然后将不构成循环的边添加到树中6 ?' A* Q/ z\" n# ~, ^, U
    
14. p=plot(G,"EdgeLabel",G.Edges.Weight);: o\" }3 p3 i) ]
    
15. highlight(p,T,"NodeColor","red","EdgeColor","red");
    3 O; h/ I5 \  i0 p\" _% W\" f. ^
16. % 将最小生成树的边设置为红色!
    3 w# E' J\" P. _3 Q. S4 e

复制代码

" O  |6 @: b8 I- ?( ?2 I3 O0 t生成的最小生成树：
3 s2 b& c0 c9 `/ U6 M
我们也可以把最小生成树的边和节点打印出来，也可以把整段路的权加起来看看：
尾声

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