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

2744557306

实际问题引入

/ J9 L# x# J( {5 ?1 l/ f( v1 N- P# g实这道题的答案，其实就是找到这个图的最小生成树。

Kruskal算法
6 z( v& N2 E4 v. F7 R+ n& t, w此算法可以称为“加边法”，初始最小生成树的边数为 0，每迭代一次就选择一条满足条件的最小代价的边，加入到最小生成树边的集合里面。
+ k% j9 K' M* ?% ?! O2 ^其实核心思想就是贪心思想：通过局部最优达到整体最优
2 ?: V# |$ S. W6 y: x( D
将所有的边权进行排序
" ~9 i' O/ V' p8 {2 j不断迭代选择权最小的边，直到所有的点被连起来（边数=节点数-1）。
5 X+ |! ^4 I( N7 v, t在迭代期间，如果边构成了环，就要丢弃该边，因为树中是不存在环的！
4 {$ h& Z3 s0 K: m( C( i整体代码展示
在matlab中，最小生成树的生成直接用minspantree()函数就行。

1. s=[1,1,1,1,2,2,3,3,4,4,5,5,6];
   4 H! C7 v* H\" W& |; w* C, @$ k
2. t=[2,3,4,5,3,6,5,7,5,6,6,7,7];$ Q& f3 k8 D% f8 ?& k+ R2 Y& H
   
3. w=[35,24,10,25,25,20,15,11,12,30,15,25,18];! i- _1 X! Z! d! Z4 O6 W. A4 ?+ v+ \. o
   
4. names={'1','2','3','4','5','6','7'};7 a9 j6 R- n# y
   
5. G=graph(s,t,w,names);
   ) F/ o+ l2 q$ a7 \' ~6 F
6. p=plot(G,"EdgeLabel",G.Edges.Weight);/ T$ m; Q# k1 I/ n4 a# B9 k3 t9 c
   
7. % 求解最小生成树9 a, c) `6 X* J; P: O
   
8. T=minspantree(G,"Method","sparse");
   , ^! B! ~: T8 n9 E
9. % sparse代表的是Kruskal算法  R; o2 e; u+ e9 U# z
   
10. % dense代表的是Prim算法6 U5 m) x/ v1 z! L8 {6 _
    
11. 0 q8 q5 p2 |2 c* W7 p4 D  t. {4 S
    
12. % sparse:Kruskal算法
    # q\" j; e$ p, q3 S
13. % 算法按权重对所有的边排序，然后将不构成循环的边添加到树中
    : |2 e/ f\" H, r: y1 Z\" a
14. p=plot(G,"EdgeLabel",G.Edges.Weight);
    # \, U) l1 X. N\" ~. S
15. highlight(p,T,"NodeColor","red","EdgeColor","red");
    % Y$ J: B4 A6 h8 g, Q' X
16. % 将最小生成树的边设置为红色!
    ' e5 d6 f$ j7 P; ]8 V1 a  y/ }

复制代码

5 Z% I3 o. e, V( V! n: {" A: ~- S
/ l# ?2 C- E; B( A) h; _  J+ z, Y% s生成的最小生成树：
$ g3 e) l, u! P1 x
我们也可以把最小生成树的边和节点打印出来，也可以把整段路的权加起来看看：
尾声

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

3 w; N7 h) e/ J3 p4 v6 k5 A. n" p$ R