数学建模社区-数学中国

标题: 【图论】【Matlab】最小生成树之Kruskal算法【贪心思想超详细详解Kruskal算法并应用】 [打印本页]

---

作者: 2744557306    时间: 2023-11-30 15:11
标题: 【图论】【Matlab】最小生成树之Kruskal算法【贪心思想超详细详解Kruskal算法并应用】
实际问题引入
9 W. D, l: |2 i! @3 x& p* T
实这道题的答案，其实就是找到这个图的最小生成树。

9 U* z! S$ ?9 |; o  S8 G0 QKruskal算法
% n" c0 h" `) h此算法可以称为“加边法”，初始最小生成树的边数为 0，每迭代一次就选择一条满足条件的最小代价的边，加入到最小生成树边的集合里面。
其实核心思想就是贪心思想：通过局部最优达到整体最优

" e, [) J' _7 O3 |( ?0 J将所有的边权进行排序
不断迭代选择权最小的边，直到所有的点被连起来（边数=节点数-1）。
在迭代期间，如果边构成了环，就要丢弃该边，因为树中是不存在环的！
  ~& \% q, C) G- J5 [整体代码展示
在matlab中，最小生成树的生成直接用minspantree()函数就行。

1. s=[1,1,1,1,2,2,3,3,4,4,5,5,6];
   
2. t=[2,3,4,5,3,6,5,7,5,6,6,7,7];
   
3. w=[35,24,10,25,25,20,15,11,12,30,15,25,18];
   - S. U: x- a1 V5 Z1 Z, e
4. names={'1','2','3','4','5','6','7'};
   7 Z3 ]5 Y* F7 J& i
5. G=graph(s,t,w,names);
   ) _6 y# K6 E  e1 R  Y
6. p=plot(G,"EdgeLabel",G.Edges.Weight);
   
7. % 求解最小生成树
   
8. T=minspantree(G,"Method","sparse");
   , I! \- j; \6 D5 @
9. % sparse代表的是Kruskal算法
   ; R/ ~: L" p. c% c+ S! L% J
10. % dense代表的是Prim算法
    * P3 ^1 g' j) \2 ^( ]
11. 
    1 i' x" {8 F9 z. `* z2 h
12. % sparse:Kruskal算法
    3 x, V8 {9 \2 R; a8 g) d/ e; f
13. % 算法按权重对所有的边排序，然后将不构成循环的边添加到树中
    
14. p=plot(G,"EdgeLabel",G.Edges.Weight);
    
15. highlight(p,T,"NodeColor","red","EdgeColor","red");
    # ?4 M7 z; e6 @6 B: p
16. % 将最小生成树的边设置为红色!
    5 C9 w) t5 @% Q

复制代码

生成的最小生成树：
) o( t& [. m4 e8 W
: v: l) r. j+ ?% O  W6 Z! h我们也可以把最小生成树的边和节点打印出来，也可以把整段路的权加起来看看：
8 g0 n3 ]& U0 c0 r# d  _0 i4 ~尾声

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

/ A6 r& e( |4 j
. U! F% `3 ]7 w1 K/ [# @& q

a6d69d91254fe9e66009999ed24b2707.png (208.21 KB, 下载次数: 199)

2023-11-30 15:04 上传

点击文件名下载附件

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5