直观理解：最小生成树算法Prime和Kruskal

  在正式讲解Prime和Kruskal算法之前，我们需要先搞明白什么是最小生成树，而搞明白最小生成树的概念之前，我们先介绍几个名词。
联通图：在一个无向图中，若任意两个顶点与之间都有最少一条路径相通，则称该无向图为连通图。
生成树：如果一个联通图联通子图包含图中所有的顶点，且任意任意两顶点之间有且仅有一条路径，则称该联通子图为联通图的生成树；
最小生成树：连通图的所有生成树中，边的权重之和最小的生成树称为最小生成树。
解释完上述名词之和，接下来我们重点介绍两种经典的最小生成树算法Prime算法和Kruskal算法。

Prime算法

  假设存在联通图，图中所有的顶点集合为，集合表示已经加入到生成树中的顶点集合，集合表示未加入到生成树中的顶点集合。一开始，随机指定一个顶点加入到集合中，则，每次从集合与集合的顶点所构成的所有边中选取权值最小的一条边作为生成树的边，并将边在集合的那个顶点加入到集合中，如此下去直到集合中的全部顶点都加入到集合集合中，得到最小生成树。算法的执行过程如下图所示：

Prime最小生成树过程

Kruskal算法

  将联通图中所有的边按其权值由小到大的次序进行排序，对边的权值按从小到大的顺序进行选取，若该边选取后与已选择的边无法形成回路，则保留当前边，否则跳过当前边，选择下一条。依次选够条边即可得到最小生成树，其中为连通图中的顶点个数。算法的执行过程如下图所示：

Kruskal最小生成树过程

总结

  1.执行Kruskal算法的图存储结构一般采用边集数组的方式进行存储，且权值相等的边在数组中排列的排列先后顺序并不影响最终最小生成树的权值总和，但可能会影响最小生成树的形状。由于需要对边进行排序和选择，因此该方法对于边相对比较多的图，运行时间较长；
  2.执行普里姆算法的图存储结构一般采用邻接矩阵的方式。该方法以某个顶点为出发点，每次选择两个集合之间权值最小的边进行最小生成树生成，较适合边较多的图的最小生成树生成，且性能较好。