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

2744557306

实际问题引入
7 j( `5 I( y/ f" X
实这道题的答案，其实就是找到这个图的最小生成树。

Kruskal算法
, D5 |; D! \- q5 O2 h  Y; [, `此算法可以称为“加边法”，初始最小生成树的边数为 0，每迭代一次就选择一条满足条件的最小代价的边，加入到最小生成树边的集合里面。
& E0 x4 M$ I" H& H: [! n0 |% E+ \其实核心思想就是贪心思想：通过局部最优达到整体最优
, O1 l% O( o- v( b% {3 X6 j, r
, c0 A3 f6 R; ]6 G: Q将所有的边权进行排序
) m" i; v5 S9 K/ Z/ d, r不断迭代选择权最小的边，直到所有的点被连起来（边数=节点数-1）。
在迭代期间，如果边构成了环，就要丢弃该边，因为树中是不存在环的！
整体代码展示
在matlab中，最小生成树的生成直接用minspantree()函数就行。

1. s=[1,1,1,1,2,2,3,3,4,4,5,5,6];5 k5 B7 `7 ~9 m7 ]5 o
   
2. t=[2,3,4,5,3,6,5,7,5,6,6,7,7];
   8 y8 b* [4 T* F: u- N
3. w=[35,24,10,25,25,20,15,11,12,30,15,25,18];
   , R, R# d, G- ~9 X- O# ], ^
4. names={'1','2','3','4','5','6','7'};, v4 n( @' a4 N9 D, v' a
   
5. G=graph(s,t,w,names);
   ( D# y4 @) {) f' }& I& V/ K
6. p=plot(G,"EdgeLabel",G.Edges.Weight);
   ! _7 A; X3 V  c1 v; f\" ]- F: L
7. % 求解最小生成树; K- Z# p. V' L: Z( h$ e
   
8. T=minspantree(G,"Method","sparse");9 ~\" K. {- ?# y0 y) |( [
   
9. % sparse代表的是Kruskal算法
   4 y$ O8 `; {/ ]' O/ j2 |* ~0 ~* f
10. % dense代表的是Prim算法2 C! a# L- _' l, ~# P
    
11. 
    . x4 ]0 U7 T! J5 z- y$ D2 ~$ V
12. % sparse:Kruskal算法
    ' D# g: I  {0 d* x
13. % 算法按权重对所有的边排序，然后将不构成循环的边添加到树中
    7 U& {1 Y& d, j6 w2 r1 X
14. p=plot(G,"EdgeLabel",G.Edges.Weight);9 |0 j# ]. N6 }. U; ?
    
15. highlight(p,T,"NodeColor","red","EdgeColor","red"); * v* |! b9 F: i  p9 \
    
16. % 将最小生成树的边设置为红色!5 O# }$ \6 u' p7 ^
    

复制代码

4 |- D+ o. ?* V. b
生成的最小生成树：

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

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

1 H. k" e1 f" Q5 k