数学建模社区-数学中国

标题: 最小生成树 [打印本页]
作者: 2744557306    时间: 2023-8-5 15:07
标题: 最小生成树
如下图所示：最小连通子图就是边要尽可能的少，但是要保持联通

. c, B7 ~7 s( N1 W4 g7 k
对于最小生成树而言如下图：边上的权值总和最小就是最小生成树。前提是要连通。

( x- I* b" ?( B( t3 b' C
已经知道最小生成树的概念之后，对于一个带权连通无向图的话，如何生成最小生成树呢？。下面有两种方法，一种是prim算法，另一种是Kruskal算法。prim算法如下图
0 T7 {) Y; Y4 n! l) t7 g" ~" n8 o2 I
对于上面的图来说，我们随机找到一个节点，例如农场，那么距离农场最近的为电站。那么我们就有了农场到电站这条线了。接下来观察这两个节点，看这两个节点连接其他节点的路线最短的。很明显农场到p城路线最短。接下来找这3个节点中距离其他节点最近的，很明显p城到学校距离最近。那么我们就有了p城到学校的线路。在4个节点中寻找距离其他节点最近的，p城到矿场最近，在5个节点中寻找最近的，矿场到渔村最近。最后路线变为。

6 i- H( ^1 w; `3 g+ t
Kruskal算法：
( x2 t! X, }* N3 B
prim算法是寻找和节点之间的最小距离，那么kruskal算法就是选择最小的边。
如上图，最短的边是学校到p城，下一个最短的是矿场到渔村，下一个最短的是农场到电站，在下一个是p城到矿场或者p城到渔村，顺便选一个就可以。之后就是农场到p城或者是学校到矿场。其中学校不能到矿场。因为会形成闭环，也就是原本这些点就已经连通了。最后结果如下：
8 @$ ]) W4 k* B3 q% p
由于图片上传有问题，所有图片都在附件中

* G# `; {+ H- U* I
/ v/ T# i1 i( F+ B5 O0 R* t

最小生成树.docx

902.61 KB, 下载次数: 0, 下载积分: 体力 -2 点



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5