最小生成树

2744557306

如下图所示：最小连通子图就是边要尽可能的少，但是要保持联通

- L) n7 u- q6 g" h, r; h+ [% O; V

对于最小生成树而言如下图：边上的权值总和最小就是最小生成树。前提是要连通。

7 u9 n& X. X5 S! G* Y. L

已经知道最小生成树的概念之后，对于一个带权连通无向图的话，如何生成最小生成树呢？。下面有两种方法，一种是prim算法，另一种是Kruskal算法。prim算法如下图

对于上面的图来说，我们随机找到一个节点，例如农场，那么距离农场最近的为电站。那么我们就有了农场到电站这条线了。接下来观察这两个节点，看这两个节点连接其他节点的路线最短的。很明显农场到p城路线最短。接下来找这3个节点中距离其他节点最近的，很明显p城到学校距离最近。那么我们就有了p城到学校的线路。在4个节点中寻找距离其他节点最近的，p城到矿场最近，在5个节点中寻找最近的，矿场到渔村最近。最后路线变为。

2 [0 n* E" Q4 y8 F0 G+ D

Kruskal算法：

3 t0 p) h/ `3 R% I" C0 h

prim算法是寻找和节点之间的最小距离，那么kruskal算法就是选择最小的边。

如上图，最短的边是学校到p城，下一个最短的是矿场到渔村，下一个最短的是农场到电站，在下一个是p城到矿场或者p城到渔村，顺便选一个就可以。之后就是农场到p城或者是学校到矿场。其中学校不能到矿场。因为会形成闭环，也就是原本这些点就已经连通了。最后结果如下：

由于图片上传有问题，所有图片都在附件中