今天是大结局，说下“图”的最后一点东西，“最小生成树“和”最短路径“。
一： 最小 生成树
1. 概念
首先看如下图，不知道大家能总结点什么。
对于一个连通图G， 如果其全部顶点和一部分边构成一个子图G1，当G1满足：
① 刚好将图中所有顶点连通。② 顶点不存在回路。则称G1就是G的“生成树”。
其实一句话总结就是：生成树是将原图的全部 顶点以最小的边连通的子图，这不，如下的连通图可以得到下面的两个生成树。
② 对于一个带权的连通图，当生成的树不同，各边上的权值总和也不同，如果某个生成树的权 值最小，则它就是“最小生成树”。
2. 场景
实际应用中“最小生成树”还是蛮有实际价值的，教科书上都有这么一句 话，若用图来表示一个交通系统，每一个顶点代表一个城市，
边代表两个城市之间的距离，当 有n个城市时，可能会有n(n-1)/2条边，那么怎么选择(n-1)条边来使城市之间的总距离最小，其实它
的抽象模型就是求“最小生成树”的问题。
3. prim算法
当然如何求“最小生 成树”问题，前人都已经给我们总结好了，我们只要照葫芦画瓢就是了，
第一步：我们建立集 合“V,U"，将图中的所有顶点全部灌到V集合中，U集合初始为空。
第二步： 我们将V1放 入U集合中并将V1顶点标记为已访问。此时：U（V1）。
第三步： 我们寻找V1的邻接点 （V2,V3,V5)，权值中发现(V1,V2)之间的权值最小，此时我们将V2放入U集合中并标记V2为已访问，
此时为U（V1，V2）。
第四步： 我们找U集合中的V1和V2的邻接边，一阵痉挛后，发现 （V1，V5）的权值最小，此时将V5加入到U集合并标记为已访问，此时
U的集合元素为（V1，V2 ，V5）。
第五步：此时我们以（V1，V2，V5）为基准向四周寻找最小权值的邻接边，发现（V5 ，V4）的权值最小，此时将V4加入到U集合并标记
为已访问，此时U的集合元素为（V1，V2，V5 ，V4）。
第六步： 跟第五步形式一样，找到了（V1，V3）的权值最小，将V3加入到U集合中并 标记为已访问，最终U的元素为（V1，V2，V5，V4，V3），