数学建模社区-数学中国

标题: 最小生成树 [打印本页]
作者: 2744557306    时间: 2023-8-5 15:07
标题: 最小生成树
如下图所示：最小连通子图就是边要尽可能的少，但是要保持联通
- H  I+ C: `/ V# k% k. v; P
对于最小生成树而言如下图：边上的权值总和最小就是最小生成树。前提是要连通。
, P7 c$ H1 J" \. n0 w0 ^
已经知道最小生成树的概念之后，对于一个带权连通无向图的话，如何生成最小生成树呢？。下面有两种方法，一种是prim算法，另一种是Kruskal算法。prim算法如下图
: g1 h, x) Q  I! L4 e: D# }
对于上面的图来说，我们随机找到一个节点，例如农场，那么距离农场最近的为电站。那么我们就有了农场到电站这条线了。接下来观察这两个节点，看这两个节点连接其他节点的路线最短的。很明显农场到p城路线最短。接下来找这3个节点中距离其他节点最近的，很明显p城到学校距离最近。那么我们就有了p城到学校的线路。在4个节点中寻找距离其他节点最近的，p城到矿场最近，在5个节点中寻找最近的，矿场到渔村最近。最后路线变为。
9 T% h1 d1 L8 {; b
Kruskal算法：

( x0 [' P9 `1 n. K& X7 k
prim算法是寻找和节点之间的最小距离，那么kruskal算法就是选择最小的边。
如上图，最短的边是学校到p城，下一个最短的是矿场到渔村，下一个最短的是农场到电站，在下一个是p城到矿场或者p城到渔村，顺便选一个就可以。之后就是农场到p城或者是学校到矿场。其中学校不能到矿场。因为会形成闭环，也就是原本这些点就已经连通了。最后结果如下：
6 W1 F' h+ f- G* z5 ]. c: ^* R
由于图片上传有问题，所有图片都在附件中
+ i2 y. f, C) ~, v* C, Y

0 g  }$ q. C2 ^& e+ v2 X  _

最小生成树.docx

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



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