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

2744557306

实际问题引入
: }. R. x6 A) w& s* Q6 p' v$ |" z
+ i+ D2 `! s  V+ g' J4 I实这道题的答案，其实就是找到这个图的最小生成树。
" k) \# V) t/ o" e
, V% c4 ?# l0 O8 O' f5 KKruskal算法
此算法可以称为“加边法”，初始最小生成树的边数为 0，每迭代一次就选择一条满足条件的最小代价的边，加入到最小生成树边的集合里面。
其实核心思想就是贪心思想：通过局部最优达到整体最优
- V6 P$ w3 {/ _
" r$ ^, E4 e) X4 s$ i2 _将所有的边权进行排序
6 {% d) Z# E+ k0 {) V4 V6 l不断迭代选择权最小的边，直到所有的点被连起来（边数=节点数-1）。
在迭代期间，如果边构成了环，就要丢弃该边，因为树中是不存在环的！
9 Z! m) u$ r1 m整体代码展示
/ J1 K: }# F9 w在matlab中，最小生成树的生成直接用minspantree()函数就行。

1. s=[1,1,1,1,2,2,3,3,4,4,5,5,6];
   1 E# C( M; r4 E+ x8 s5 E
2. t=[2,3,4,5,3,6,5,7,5,6,6,7,7];0 q8 \/ F. ?( E- f0 [* A7 m- L
   
3. w=[35,24,10,25,25,20,15,11,12,30,15,25,18];( a1 A3 d2 k3 L# e. G+ @: ?
   
4. names={'1','2','3','4','5','6','7'};
   $ K5 H9 _4 Y) }  U: X' W
5. G=graph(s,t,w,names);% G0 E/ W5 g0 [) a
   
6. p=plot(G,"EdgeLabel",G.Edges.Weight);, ~5 O6 R4 ^$ U3 T
   
7. % 求解最小生成树\" D, n& Z. M) w( Q( x$ C0 m
   
8. T=minspantree(G,"Method","sparse");# z$ e9 M  f4 k0 H
   
9. % sparse代表的是Kruskal算法
   * t. \4 p; b& c. m, P% G/ E
10. % dense代表的是Prim算法+ v9 p' d% C; n: A
    
11. 4 {% t9 ?( x6 `: u5 T- i
    
12. % sparse:Kruskal算法
    7 y  T* w1 V, W6 v9 L# f8 H
13. % 算法按权重对所有的边排序，然后将不构成循环的边添加到树中) Y( K9 q7 R' V, ^* ]\" A5 j
    
14. p=plot(G,"EdgeLabel",G.Edges.Weight);
    3 `$ K8 E! Y4 }! L& I& ~3 I
15. highlight(p,T,"NodeColor","red","EdgeColor","red"); - j! Y2 N8 t& a8 w0 n, x# |
    
16. % 将最小生成树的边设置为红色!7 n1 o& C8 s& j5 E2 H
    

复制代码

& {% y1 d1 p+ M6 \* q, b' u; H生成的最小生成树：
) {# D8 s) L7 t; C$ f0 m
我们也可以把最小生成树的边和节点打印出来，也可以把整段路的权加起来看看：
尾声

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

% Z9 ^1 L( B7 q: z- q" N( y