生成树的性质
（1）每个连通图至少包含一颗生成树；
（2）生成树中不存在环,但给生成树添加一条边就会构成环；
（3）删除生成树中的任意一条边都会导致图的不连通；
（4）n个顶点的连通图，生成树包含n个顶点和n-1条边；
（5）n个顶点的无向完全图最多包含n^n-2颗生成树。
最小生成树对于图G(V,E)，最小生成树T是E的无环子集。包含所有顶点V，并且边权重之和最小。没错，那下一步就到了算法了，最小生成树算法有很多，其中最经典的就是克鲁斯卡尔（Kruskal）算法和普里姆（Prim）算法。从策略上来说，Prim算法是直接查找，多次寻找邻边的权重最小值；Kruskal算法是先对权重排序后查找。所以说，Kruskal算法在效率上是要比Prim快的，因为Kruskal只需一次对权重的排序就能找到最小生成树，而Prim算法需要多次对邻边排序才能找到。在这里，就只对prim算法进行讨论了。Prim算法的实现过程是以一个结点作为最小生成树的初始结点，然后以迭代的方式找出最小生成树中各结点权重最小的边，并加到最小生成树中。当所有的结点都加入到最小生成树中后，就找出了这个连通图的最小生成树。那我们就简单粗暴的用例子来理解prim算法，下图是一个图，假设从A点出发，我们来寻找一下它的最小生成树。假如从顶点A出发，顶点B、C的权值分别为2、3，所以对于顶点A来说，到顶点B的权值最小，将顶点B加入到生成树中：继续分析与顶点A和B相邻的所有顶点（包括C、D、E），其中权值最小的是顶点C、D，和前边的算法一样，假设一下就好了。假设将C添加到生成树当中：继续分析与生成树中已添加顶点相邻的顶点中权值最小的顶点，发现为节点D，则添加到生成树中：继续分析与生成树中已添加顶点相邻的顶点中权值最小的顶点，发现节点E，则添加到生成树中：继续分析与生成树中已添加顶点相邻的顶点中权值最小的顶点，发现节点F，则添加到生成树中：最后就剩下了节点G了，我们的算法过程就结束了。这个算法的图解过程是不是很清晰呢，老规矩，下边我们就要进入Prim的算法实现了。frompythonds.graphsimportPriorityQueue,Graph,Vertexdefprim(G,start):pq=PriorityQueue()forvinG:v.setDistance(sys.maxsize)v.setPred(None)start.setDistance(0)pq.buildHeap([(v.getDistance(),v)forvin6])whilenotpq.isEmpty():currentVert=pq.delMin()fornextVertincurrentVert.getConnections():newCost=currentVert.getweight(nextVert)+currentVert.getDistance()ifvinpqandnewCostnextVert.getDistance():nextVert.setPred(currentVert)nextVert.setDistance(newCost)pq.decreasekey(nextVert,newCost)好了，我的笔记到这里就要和大家说再见了，从年12月25日开始在