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

2744557306

实际问题引入
, H; E/ G+ u. y6 v+ P0 ?' i
5 e3 l. h) l- o* Q实这道题的答案，其实就是找到这个图的最小生成树。

Kruskal算法
此算法可以称为“加边法”，初始最小生成树的边数为 0，每迭代一次就选择一条满足条件的最小代价的边，加入到最小生成树边的集合里面。
其实核心思想就是贪心思想：通过局部最优达到整体最优

将所有的边权进行排序
; H1 }" a( H: B4 [- S4 [/ x4 I不断迭代选择权最小的边，直到所有的点被连起来（边数=节点数-1）。
4 U) ]! ?0 j0 I" f1 C在迭代期间，如果边构成了环，就要丢弃该边，因为树中是不存在环的！
5 n7 v$ b2 _% l) P& p整体代码展示
在matlab中，最小生成树的生成直接用minspantree()函数就行。

1. s=[1,1,1,1,2,2,3,3,4,4,5,5,6];2 k8 U4 H3 k( w& t+ ]: b
   
2. t=[2,3,4,5,3,6,5,7,5,6,6,7,7];. k+ b. Q2 V* [, P$ K
   
3. w=[35,24,10,25,25,20,15,11,12,30,15,25,18];
   , }. B0 y\" k' c2 P- }
4. names={'1','2','3','4','5','6','7'};
   7 e3 w/ h) d: s3 _$ R
5. G=graph(s,t,w,names);! W8 e+ ]2 {; w2 Y2 V2 q1 c
   
6. p=plot(G,"EdgeLabel",G.Edges.Weight);! j* D' b1 l% P
   
7. % 求解最小生成树' H* E$ e! {, q% u# ]# w
   
8. T=minspantree(G,"Method","sparse");. H# Q7 D6 l* L1 X* ?$ h7 E; ?+ ^
   
9. % sparse代表的是Kruskal算法
   . i4 _- R! ^( R# Z
10. % dense代表的是Prim算法
    8 K4 w# p2 S3 y9 n
11. 
    % Y/ t/ C0 a* ~2 y1 f  w
12. % sparse:Kruskal算法
    7 [8 o) \8 d. N1 H9 ^5 A
13. % 算法按权重对所有的边排序，然后将不构成循环的边添加到树中
    2 _& `  `# B, w+ X
14. p=plot(G,"EdgeLabel",G.Edges.Weight);* ^- e6 [, `2 f; c. U) B% F2 r+ z
    
15. highlight(p,T,"NodeColor","red","EdgeColor","red"); ! J3 u8 U! o1 n, X; u
    
16. % 将最小生成树的边设置为红色!$ S8 d5 J4 G3 I) v. I0 o5 H! Y
    

复制代码

生成的最小生成树：
+ R( O0 l) F5 {9 j: x) c
我们也可以把最小生成树的边和节点打印出来，也可以把整段路的权加起来看看：
( R& n& [% u6 q0 s4 i尾声

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

, l# g$ ^2 G6 y$ ?% G