实际问题引入( c( U8 w: I! a* X/ n/ C4 _1 S2 S
# \2 w4 H' W. Z. O! o实这道题的答案,其实就是找到这个图的最小生成树。
- l6 h- U# J& U# E/ \0 t/ Y: ^* ~5 s! ^4 q* n( r
Kruskal算法% O& K+ E2 H# A8 G# J& Z
此算法可以称为“加边法”,初始最小生成树的边数为 0,每迭代一次就选择一条满足条件的最小代价的边,加入到最小生成树边的集合里面。, N1 k2 R; Z/ A5 P' ~
其实核心思想就是贪心思想:通过局部最优达到整体最优
' |) E- P: Y: e& k( f! P0 o# n( E, `, k, `5 d
将所有的边权进行排序 H! T& |/ t5 _3 \( R8 g. V) `5 r
不断迭代选择权最小的边,直到所有的点被连起来(边数=节点数-1)。
$ a$ ?. N) E+ o! z8 m9 p! z! q2 ]在迭代期间,如果边构成了环,就要丢弃该边,因为树中是不存在环的!- ^! ` X2 N8 z6 Z0 q
整体代码展示
/ g1 w& l0 E1 ~+ o在matlab中,最小生成树的生成直接用minspantree()函数就行。- s=[1,1,1,1,2,2,3,3,4,4,5,5,6];
7 H8 D0 P& k- ^3 Y* ] - t=[2,3,4,5,3,6,5,7,5,6,6,7,7];
. i! f3 Y: g! r+ i. r4 v - w=[35,24,10,25,25,20,15,11,12,30,15,25,18];3 `6 s' f; ?5 ~5 B7 m$ k
- names={'1','2','3','4','5','6','7'};; d% Q a1 o% P( q8 h
- G=graph(s,t,w,names);
7 v; ?: N! Q. a - p=plot(G,"EdgeLabel",G.Edges.Weight);) x, n' J8 a2 T1 ]6 ^: y- g
- % 求解最小生成树
% E9 K5 S9 e4 q9 D- {% J - T=minspantree(G,"Method","sparse");
7 T9 Y1 s* c9 \\" t& S5 F - % sparse代表的是Kruskal算法
; @: ~7 j: G1 c2 J - % dense代表的是Prim算法; F& _6 V9 s- U+ {: _4 P: V
% _9 O\" T. R4 A$ `& y* c7 q- m- % sparse:Kruskal算法
4 s! n/ `( X' ~: J) V - % 算法按权重对所有的边排序,然后将不构成循环的边添加到树中* p& y1 L/ A4 A1 v1 ^
- p=plot(G,"EdgeLabel",G.Edges.Weight);
: e- f; a1 z\" ]! F, ~ - highlight(p,T,"NodeColor","red","EdgeColor","red"); ! k5 b7 H5 H! q( R
- % 将最小生成树的边设置为红色!+ n6 |) E, Q' |* ]\" t. N
复制代码
2 ~% e7 I9 Z: `5 r4 I; [: u7 n; ?. t$ ^3 g. @
生成的最小生成树:
+ h. X( M( {5 A; i' y' ^
/ g; Z3 n7 {0 M& q我们也可以把最小生成树的边和节点打印出来,也可以把整段路的权加起来看看:
# H3 K2 L. E4 p8 k8 h尾声看到这里,相信我们已经学会Kruskal算法寻找最小生成树的过程了,当然,这离数学建模的要求,离我们的目标还非常遥远,博主在不断学习的过程中,也希望可以通过分享学习日记的方式带动大家!
- R1 P" U# M) o- x# p: H: `2 B! T4 q0 @9 d2 k$ Y
|