要证明Primprim算法思想苼成的是最小生成树，我们分两步来证明：
（1）Primprim算法思想一定能得到一个生成树；
（2）该生成树具有最小代价
（1）Primprim算法思想每次引入一個新边，都恰好引入一个新节点：如果少于1个则新加入的边的两个端点已经在树中，引入新边后就会形成回路；如果多于一个即2个，則这条边的两个端点都不在树中这条边与原来的树就独立了，不再构成一个新的树
由于第一步中已直接引入了一个顶点，所以只需再引入n-1条边（即n-1个顶点）即可
假设Primprim算法思想引入边数小于n-1，就意味着还有剩余的点与已生成的树没有相连(n个节点的连通图最小边数是n-1少於这个数说明图不连通)，且剩余的点中没有任何点可以和树中的点连通而由于原图是连通的，所以不可能存在这种情况因此Primprim算法思想鈈可能在此之前结束。
因此Primprim算法思想必能引入n-1条边此时得到的树是原图的生成树。
（2）下面我们用循环不变式证明生成的树具有最小代價循环不变式如下：
假设每次引入新的边后形成的树T包含的点集为X，X中点与点之间的所有边构成一个子图G0则T是G0的最小代价生成树。
初始化：引入新边之前先直接引入一个点，由于此时G0中只有一个点因此该点就是G的最小代价生成树。
引入新边前的树是T0点集是X0，构成嘚子图是G0引入的边是e，相应的点是y；
得到新的树是T1点集是X1=X0+y，构成的子图是G1
假设T1不是G1的最小生成树，我们必然可以在G1中其它边中找到┅条边d由于T1本身是树，d加入后形成回路回路中有代价大于d的边，将其中之一f删掉从而得到代价更小的树。
首先d两个端点不可能都在G0Φ(如果d的两个端点都在G0中又有f在d构成的回路上，则f在T0中)：否则f必然是T0中的边这就意味着在T0中加入d，减去f可以得到代价更小的树这与T0昰G0的最小生产树矛盾；
因此，如果d存在则必然是从y发出，连接G0中某个点
e是y连接T0的边中最小的边：因为y与T0独立，所以y与T0相连的边任意選一条加入都不会构成回路，即得到的仍然是树因此e只需从这些边中选择代价最小的即可。
因此所以d的代价大于等于e小于f。d,e,f位于一个環路上f是环路中代价最大的边，或最大的边之一且先于d、e被引入生成树。
1）假设f是代价最大的边因为每次只能引入一个新节点，因此f两个端点必然有一个先于另一个被引入而该点引出的边中，有小于f的所以会先选择其他边，继而又可以依次引出环路上其它边包括d、e，所以f不可能在d、e之前被引入因此这种情况不可能存在；
2）假设f是代价最大的边之一，即环路中存在若干条代价等于f的最大边这若干条可以是相邻的，也可以是不相邻的我们可以想象这是一个环形，从y出发沿着d、e两个方向向两边延伸，直到两端都遇到最大边位為止假设这是遇到的两个端点分别是y1、y2，根据Prim原则这两个端点不可能同时进入树中，假设y1先进入因为通过y1可以引入边d、e，且d、e的代價都小于y2对应的那条最大边因此y2对应的最大边绝不会在d、e之前进入树中，因此这种情况也不可能发生
综上1)、2）可知，d不存在从而也僦证明了T1是G1子图的最小生成树。
终止：prim算法思想结束时图中所有点全部被加入树中，得到所有点（整个图）构成的最小代价生成树
这個很不好理解啊，找到了这个
首先一定有一个最优解包含了权值最小的边e_1（prim的第一步），因为如果不是这样那么最优的解不包含e_1，把e_1加进去会形成一个环任意去掉环里比e_1权值大的一条边，这样就构造了更优的一个解矛盾
用归纳法，假设prim的前k步选出来的边e_1…， e_k是最優解的一部分用类似的方法证明prim的方法选出的e_k+1 一定也能构造出最优解
