基本概念：

由生成树定义可知，无向连通图的生成树不是唯一 的，于是最小生成树的定义诞生，即：无向连通图是一个带权图，她的所有生成树中必有一棵边的权值总和最小的生成树（称为：最小代价生成树，即：最小生成树）

综合来说：Prim算法时间复杂度（O(n^n)）当顶点较少时选择； Kruskal算法时间复杂度（O(e*loge)）主要耗费在边的排序上，故当边较少时适合选择

基本概念：

简单来说：Prim算法就是以点为出发点，通过某一顶点不断寻找相对权值最小的边构造最小生成树，时间复杂度（O(n^2)）

基本思想：

一张图秒懂（转载的。。。） 设置两个集合： 集合U表示用于存放最小生成树的顶点 集合T表示用于存放最小生成树的边

图中u表示已经访问过的顶点、v表示还未访问的顶点 为实现Prim算法，需考虑如何表示最小生成树 书上设置的三个辅助向量（即：数组）：cost[N]、 tree[N]、 vis[N] 其中： cost[]数组：用来保存最终最小生成树每条边的权值； tree[]数组：对应于cost[]数组，例如：tree[4]=1;说明当前这条边是(1,4)，即：用顶点v1连通的顶点v4，其权值为cost[4]； vis[]数组：即标记数组，判断顶点是否被访问（是否进入集合U）；

题目描述： 某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

输入： 测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。 当N为0时，输入结束，该用例不被处理。

输出： 对每个测试用例，在1行里输出最小的公路总长度。

样例输入： 8 1 2 42 1 3 68 1 4 35 1 5 1 1 6 70 1 7 25 1 8 79 2 3 59 2 4 63 2 5 65 2 6 6 2 7 46 2 8 82 3 4 28 3 5 62 3 6 92 3 7 96 3 8 43 4 5 28 4 6 37 4 7 92 4 8 5 5 6 3 5 7 54 5 8 93 6 7 83 6 8 22 7 8 17 0

样例输出： 82

代码如下：