最小生成树

2744557306

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

% J* E$ M7 Y9 M2 E. _) \( ?

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

* Z' u/ v4 ~6 F2 j+ f

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

6 g0 ^3 @3 M6 @$ k( Z

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

Kruskal算法：

- q% z6 {+ ]& p, T3 u

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

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

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