如图假设v0到v8表示9个村庄，现在需要在这9个村庄假设通信网络。村庄之间的数字代表村庄之间的直线距离，求用最小成本完成这9个村庄的通信网络建设。

• 这幅图只一个带权值的图，即网结构。

• 所谓最小成本，就是n个顶点，用n-1条边把一个连通图连接起来，并且使权值的和最小。

如果无向连通图是一个网图，那么它的所有生成树中必有一颗是边的权值总和最小的生成树，即最小生成树。

找到连通图的最小生成树，有两种经典的算法：普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法

• 从图中某一个顶点出发(这里选V0)，寻找它相连的所有结点，比较这些结点的权值大小，然后连接权值最小的那个结点。（这里是V1）

• 然后将寻找这两个结点相连的所有结点，找到权值最小的连接。（这里是V5）.

• 重复上一步，知道所有结点都连接上。

• 创建了两个数组adjvex和lowcost。adjvex[0] = 0意思就是从V0开始，lowcost[0] = 0表示V0已经被纳入到最小生成树中。之后凡是lowcost数组中的值被设置为0就是表示此下标的顶点被纳入最小生成树。

• 普里姆算法的时间复杂度为O(n^2)，因为是两层循环嵌套。

普里姆算法是从某一顶点为起点，逐步找各个顶点最小权值的边来构成最小生成树。那我们也可以直接从边出发，寻找权值最小的边来构建最小生成树。不过在构建的过程中要考虑是否会形成环的情况

在直接用边来构建最小生成树的时候，需要用到边集数组结构，代码为：

• 先构建边集数组，并排序，所以前面有对权值进行排序的方法sort。

克鲁斯卡尔(Kruskal)算法主要针对边来展开，边数较少时效率非常高，所以对于稀疏图有很大的优势；

普里姆(Prim)算法对于稠密图，边数非常多的情况更好一些。