实际问题引入( w6 N1 P& l k/ H7 L! v
" V0 q" r9 c5 L' U
实这道题的答案,其实就是找到这个图的最小生成树。9 i/ g8 \1 H; Y% M
. i) k2 q4 I1 n- M6 ?$ S- X
Kruskal算法
4 j, d0 k: a- T此算法可以称为“加边法”,初始最小生成树的边数为 0,每迭代一次就选择一条满足条件的最小代价的边,加入到最小生成树边的集合里面。
5 g7 Q6 @5 C! A! S a; A% {9 }其实核心思想就是贪心思想:通过局部最优达到整体最优
$ g5 R6 h( H* @* ~8 }$ ]! v+ m- d- x8 g* b% r
将所有的边权进行排序
8 n4 h7 f- f$ X. Q9 c! ^$ R- E/ I5 n5 k不断迭代选择权最小的边,直到所有的点被连起来(边数=节点数-1)。
: h9 o- _5 K4 |. R+ k在迭代期间,如果边构成了环,就要丢弃该边,因为树中是不存在环的!& g+ F1 O- p2 |) S% z7 q
整体代码展示
4 Q7 k+ ~; ?! P% W+ d' d在matlab中,最小生成树的生成直接用minspantree()函数就行。- s=[1,1,1,1,2,2,3,3,4,4,5,5,6];
. k) i. q2 z: E& s4 o6 d0 C - t=[2,3,4,5,3,6,5,7,5,6,6,7,7];: h. O% i# F7 @% t0 v, H- e; [
- w=[35,24,10,25,25,20,15,11,12,30,15,25,18];# Z( p) I# ]+ q+ C
- names={'1','2','3','4','5','6','7'};
2 |2 Y* g, e/ {\" S: {9 w - G=graph(s,t,w,names);
' \+ a0 S8 o+ r - p=plot(G,"EdgeLabel",G.Edges.Weight);
8 s! ~) M/ o7 Q4 D n* m - % 求解最小生成树
# Q4 S& p% R+ s0 A6 B - T=minspantree(G,"Method","sparse");
6 j1 `& E, T+ E1 M8 \* Z& V - % sparse代表的是Kruskal算法 [( ?9 B) a3 n6 ?* Z
- % dense代表的是Prim算法 b7 Z' `, `0 U' j, @- j
' _3 D! d8 p* y8 F* `- % sparse:Kruskal算法
3 x% N- Y3 h) x7 V% D - % 算法按权重对所有的边排序,然后将不构成循环的边添加到树中$ ~ P T3 j\" ]$ n/ p
- p=plot(G,"EdgeLabel",G.Edges.Weight);
5 k9 |: M2 X4 @% k - highlight(p,T,"NodeColor","red","EdgeColor","red"); 8 X1 D/ }% E! e6 r( z\" e* o+ v
- % 将最小生成树的边设置为红色!
7 d2 F* O2 Q- y
复制代码
h+ b3 Q4 a. m9 V M, \0 v9 L
0 t) c, q# k) L% d; B生成的最小生成树:
1 Q9 l6 y$ g& a7 o# e6 ]8 a
! o5 V. d6 f" {" v7 N5 k# V我们也可以把最小生成树的边和节点打印出来,也可以把整段路的权加起来看看:
; N# v3 B: b- Y4 ^4 A9 @$ R尾声看到这里,相信我们已经学会Kruskal算法寻找最小生成树的过程了,当然,这离数学建模的要求,离我们的目标还非常遥远,博主在不断学习的过程中,也希望可以通过分享学习日记的方式带动大家!
# d* N" y5 w; m. X% y% }; V5 U' Y2 L' P- B, d; T+ L
|