实际问题引入
& g8 l1 A1 w! h& q8 ]' q) d
& N( ]" q7 S4 V; a7 c7 p; p实这道题的答案,其实就是找到这个图的最小生成树。: R& N6 y5 @' _0 w" D2 c3 } g
, E1 H# a" m* N7 V4 @2 h% j$ sKruskal算法8 g0 ~: i3 X E0 m
此算法可以称为“加边法”,初始最小生成树的边数为 0,每迭代一次就选择一条满足条件的最小代价的边,加入到最小生成树边的集合里面。# D) n" a7 w8 l
其实核心思想就是贪心思想:通过局部最优达到整体最优
7 v6 l( Y8 x! N$ p0 Z- ~, { u( E1 C* \) F8 x+ @3 Y7 T( J
将所有的边权进行排序
: M7 t- u( j: A不断迭代选择权最小的边,直到所有的点被连起来(边数=节点数-1)。
+ _, c$ {0 E' U3 t7 q在迭代期间,如果边构成了环,就要丢弃该边,因为树中是不存在环的!! u6 M+ Y& j. u1 ]% D1 _- O; V7 p
整体代码展示
9 M& M4 {# w- }$ G在matlab中,最小生成树的生成直接用minspantree()函数就行。- s=[1,1,1,1,2,2,3,3,4,4,5,5,6];
\" h8 i6 ]- d/ g' \9 n+ D7 H - t=[2,3,4,5,3,6,5,7,5,6,6,7,7];
8 |/ s& }/ X7 t3 D: y - w=[35,24,10,25,25,20,15,11,12,30,15,25,18]; _ z1 A# n- c2 Y) x
- names={'1','2','3','4','5','6','7'};: h, o5 R/ s2 o3 t
- G=graph(s,t,w,names);- |( D\" v* j. j4 r. b
- p=plot(G,"EdgeLabel",G.Edges.Weight);1 s0 r9 b+ ~- v2 y. w
- % 求解最小生成树
/ U9 L) s# n$ @ - T=minspantree(G,"Method","sparse");7 L2 t0 [# u9 ~6 v7 X3 G
- % sparse代表的是Kruskal算法8 g. T\" j' S0 O1 n- i3 B
- % dense代表的是Prim算法: C/ m1 [\" e$ @, r+ q8 ]3 _
& I( H4 U! S+ u& |- % sparse:Kruskal算法6 P/ `9 b' g: l; b2 d+ X4 T! x
- % 算法按权重对所有的边排序,然后将不构成循环的边添加到树中, E9 {/ q `7 x( `! S
- p=plot(G,"EdgeLabel",G.Edges.Weight);4 Q y' k7 D$ Y/ W4 W; t' _# }$ q+ w. }
- highlight(p,T,"NodeColor","red","EdgeColor","red");
9 {1 z3 B9 ~; L a - % 将最小生成树的边设置为红色!! ~3 @6 m\" o( O' n# b' W. v
复制代码
3 n( _ i% O x, t% R4 H
6 Z* b0 E( L* x% X& _; B9 M, V0 {生成的最小生成树:- t5 P$ Q( S2 m0 k- x( g
) q1 F" h5 m3 G5 Q我们也可以把最小生成树的边和节点打印出来,也可以把整段路的权加起来看看:
5 J( s7 F: Q/ s. `9 r+ l
尾声看到这里,相信我们已经学会Kruskal算法寻找最小生成树的过程了,当然,这离数学建模的要求,离我们的目标还非常遥远,博主在不断学习的过程中,也希望可以通过分享学习日记的方式带动大家! 1 _8 k6 `. z' K
4 M; i: e+ ?1 S9 s& m R
|