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

2744557306

实际问题引入

1 n0 a9 A6 ~; Y实这道题的答案，其实就是找到这个图的最小生成树。

* E- X, s9 J$ ?6 r- kKruskal算法
9 d3 |  r/ h7 I* `4 G此算法可以称为“加边法”，初始最小生成树的边数为 0，每迭代一次就选择一条满足条件的最小代价的边，加入到最小生成树边的集合里面。
: i* N2 h; r, T1 ^6 z& ]其实核心思想就是贪心思想：通过局部最优达到整体最优
8 d2 e* X& n( U4 h: u  Y1 y
/ I) Z0 x9 _/ I将所有的边权进行排序
6 i; ]% {4 e/ _9 l; B不断迭代选择权最小的边，直到所有的点被连起来（边数=节点数-1）。
在迭代期间，如果边构成了环，就要丢弃该边，因为树中是不存在环的！
整体代码展示
在matlab中，最小生成树的生成直接用minspantree()函数就行。

1. s=[1,1,1,1,2,2,3,3,4,4,5,5,6];
   + }\" k  T) H4 k1 P8 I
2. t=[2,3,4,5,3,6,5,7,5,6,6,7,7];5 l# y# z2 V0 Z0 ~0 O1 W/ b
   
3. w=[35,24,10,25,25,20,15,11,12,30,15,25,18];
   % H/ q8 `4 \\" y; ~6 E' H
4. names={'1','2','3','4','5','6','7'};2 b, n7 L3 h: C+ V1 ]\" A% w
   
5. G=graph(s,t,w,names);
   1 g0 D; m5 W5 P% v\" @0 ~# o+ f
6. p=plot(G,"EdgeLabel",G.Edges.Weight);
   + {: E& u! d; i5 G  |2 J
7. % 求解最小生成树
   ( m0 `- R5 f3 p' C2 z7 V1 R
8. T=minspantree(G,"Method","sparse");
   4 ]5 \/ k. n; u% T3 U2 n7 s
9. % sparse代表的是Kruskal算法
   9 d4 u- \! ?. q8 S) `% {- P3 v
10. % dense代表的是Prim算法
    9 R$ q0 \- g0 u1 ]8 k: r! k% x1 r' g
11. 
    & s4 R9 X( U+ a# j. F0 m9 Q. c
12. % sparse:Kruskal算法
    * l; Z& F\" c# x
13. % 算法按权重对所有的边排序，然后将不构成循环的边添加到树中
    & Q: I; _\" A4 G* A
14. p=plot(G,"EdgeLabel",G.Edges.Weight);4 _- u2 I: ^/ F
    
15. highlight(p,T,"NodeColor","red","EdgeColor","red");
    5 \; j: Z% x7 X8 h1 `6 H+ H) T
16. % 将最小生成树的边设置为红色!$ z7 Q& B8 d% X3 A5 D  c4 Q! g
    

复制代码

! L  p2 b, ~, l0 K( E% u生成的最小生成树：

% u  ]8 y) U  L5 h9 S我们也可以把最小生成树的边和节点打印出来，也可以把整段路的权加起来看看：
' g4 b; ^- Y5 a* {% d8 m尾声

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

" O" {: u8 {+ t% z
& g2 X5 m1 l( g7 ]5 d3 J% U% F  R