最小生成树是图论问题中很基本的一个操作。常用的算法有Prim和Kruskal两种算法。本文对这两种算法稍作区别与讨论。

Prim算法是依赖于点的算法。它的基本原理是从当前点寻找一个离自己（集合）最近的点然后把这个点拉到自己家来（距离设为0），同时输出一条边，并且刷新到其他点的路径长度。俗称，刷表。 根据Prim算法的特性可以得知，它很适合于点密集的图。通常在教材中，对Prim算法进行介绍的标程都采用了邻接矩阵的储存结构。这种储存方法空间复杂度N^2，时间复杂度N^2。对于稍微稀疏一点的图，其实我们更适合采用邻接表的储存方式，可以节省空间，并在一定条件下节省时间。

Kruskal算法是依赖边的算法。基本原理是将边集数组排序，然后通过维护一个并查集来分清楚并进来的点和没并进来的点，依次按从小到大的顺序遍历边集数组，如果这条边对应的两个顶点不在一个集合内，就输出这条边，并合并这两个点。 根据Kruskal算法的特性可得，在边越少的情况下，Kruskal算法相对Prim算法的优势就越大。同时，因为边集数组便于维护，所以Kruskal在数据维护方面也较为简单，不像邻接表那样复杂。从一定意义上来说，Kruskal算法的速度与点数无关，因此对于稀疏图可以采用Kruskal算法。

那么究竟如何获得一种权衡的方法，既能应付稀疏图又能应付密集图呢？很简单，把两个算法都写到程序中，并且在行动之前判断一下点数边数的比例，如果达到某个临界值，就采用某种算法。当然，这样确实在实际行动中较为麻烦。

以下我们给出一道例题，用Prim和Kruskal算法分别解决该问题：