数学建模社区-数学中国

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

, a7 `. @/ J# u. N/ T* }7 p" W
对于最小生成树而言如下图：边上的权值总和最小就是最小生成树。前提是要连通。
4 z+ e  _6 X: h' b
已经知道最小生成树的概念之后，对于一个带权连通无向图的话，如何生成最小生成树呢？。下面有两种方法，一种是prim算法，另一种是Kruskal算法。prim算法如下图
% K* K- j- j% J
对于上面的图来说，我们随机找到一个节点，例如农场，那么距离农场最近的为电站。那么我们就有了农场到电站这条线了。接下来观察这两个节点，看这两个节点连接其他节点的路线最短的。很明显农场到p城路线最短。接下来找这3个节点中距离其他节点最近的，很明显p城到学校距离最近。那么我们就有了p城到学校的线路。在4个节点中寻找距离其他节点最近的，p城到矿场最近，在5个节点中寻找最近的，矿场到渔村最近。最后路线变为。

0 u. Y. _% _1 w+ e; q2 v. ]
Kruskal算法：
0 k/ ]3 R# H; h+ Y- }% k; u
prim算法是寻找和节点之间的最小距离，那么kruskal算法就是选择最小的边。
如上图，最短的边是学校到p城，下一个最短的是矿场到渔村，下一个最短的是农场到电站，在下一个是p城到矿场或者p城到渔村，顺便选一个就可以。之后就是农场到p城或者是学校到矿场。其中学校不能到矿场。因为会形成闭环，也就是原本这些点就已经连通了。最后结果如下：
4 A! x2 R9 M5 q/ x+ ?) A4 {+ C
由于图片上传有问题，所有图片都在附件中
* q2 N6 W( U% B& x; Q* D3 x; V
& }6 C6 V, A0 ]" B4 _, j

最小生成树.docx

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



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