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

2744557306

实际问题引入

. @5 U0 j: W: s: ^实这道题的答案，其实就是找到这个图的最小生成树。

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

9 z( o! Q6 K/ v& W8 L4 B将所有的边权进行排序
不断迭代选择权最小的边，直到所有的点被连起来（边数=节点数-1）。
8 V) d% v9 h- \. x9 K在迭代期间，如果边构成了环，就要丢弃该边，因为树中是不存在环的！
4 Z0 W5 u$ [; x) w' T0 @8 ], ]  q整体代码展示
& Y2 v8 }! E0 e/ \: G在matlab中，最小生成树的生成直接用minspantree()函数就行。

1. s=[1,1,1,1,2,2,3,3,4,4,5,5,6];
   * ^8 U5 O1 Y. S' \
2. t=[2,3,4,5,3,6,5,7,5,6,6,7,7];\" g' x3 b% A% Q8 [6 A! Y) i$ g
   
3. w=[35,24,10,25,25,20,15,11,12,30,15,25,18];
   - m6 S+ D: V; h7 T, S' u
4. names={'1','2','3','4','5','6','7'};
   8 Z6 b. b5 q) M* o! q/ Z
5. G=graph(s,t,w,names);
   ! \& {) e( _& Q3 S/ T
6. p=plot(G,"EdgeLabel",G.Edges.Weight);
   \" o/ K' z/ @! |3 Z
7. % 求解最小生成树4 |6 g/ i\" w( r
   
8. T=minspantree(G,"Method","sparse");
   - b5 k\" L- c, m, y5 x1 m1 o
9. % sparse代表的是Kruskal算法
   + U6 f2 S5 k; i\" j! ?2 p
10. % dense代表的是Prim算法1 c3 E7 c. b4 I( k& f
    
11. 
    0 ~5 j  O) O9 z) y$ r. Y
12. % sparse:Kruskal算法0 ^- E* h5 Y: O
    
13. % 算法按权重对所有的边排序，然后将不构成循环的边添加到树中
    % U- y8 Q1 D% b% F
14. p=plot(G,"EdgeLabel",G.Edges.Weight);) Z* u/ C0 t( }5 E0 t- P. X\" S2 p
    
15. highlight(p,T,"NodeColor","red","EdgeColor","red");
    & J: S0 }! o* D9 R; i9 x\" {1 g
16. % 将最小生成树的边设置为红色!
    \" r. e2 |( }9 i- r

复制代码

2 ?! u1 H) L. U+ M( T! m0 F
生成的最小生成树：
- W& M9 q2 \  S
$ e7 O8 p' a. A' V/ M8 n" o' |我们也可以把最小生成树的边和节点打印出来，也可以把整段路的权加起来看看：
尾声

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

3 G2 n, v. Z  r9 S
& l% L7 R/ f3 u6 w% N0 k! @