为啥Prim算法求出的就是最小生成树
简单给你证明一下吧用prim算法得出的边分别为e1，e2，en；依次加入的点为p1，p2，pn；若不存在最小生成树包含e1，那么把e1加入任意一颗最小生成树，必然成环，并且在环上可以找到一条不小于e1的边，（因为成环了，所以环上的点必然至少链接了两条边，而e1是p1所链接的最小的边）删掉此边，得到一颗更优的生成树或者得到了一颗包含e1的最小生成树，矛盾。若包含e1的最小生成树都不包含e2，那么把e2加入其中一颗包含e1的最小生成树中，也会成环，并且在环中也能找到不小于e2的边（因为成环了，所以顶点1顶点2所形成的集合必然包含至少三条边，而e2是当中第二小的），同上也会产生矛盾。同上可以证明prim算法得到的是最小生成树。
■网友
数据结构的书中已经给出了证明提示：
严奶奶的书中有一个MST性质：：设G=(V，E)是一个连通网络，U是顶点集V的一个真子集。若(u，v)是G中一条“一个端点在U中(例如：u∈U)，另一个端点不在U中的边(例如：v∈V-U)，且(u，v)具有最小权值，则一定存在G的一棵最小生成树包括此边(u，v)。
这个性质严奶奶也证明了，这里就不给予证明。
这里用这个性质来证明Prim算法得出的树就是最小生成树：
下面是一棵用Prim算法构成得出的生成树：
Prim算法构成生成树的思想：
先任意选取一个顶点u，这个顶点u组成一个非空集合U，图中剩下的顶点组成另一个集合V-U，其中V是图中所有顶点的集合，Prim算法选取了带权最小的连边(u,v)，其中v是属于集合V-U的，这条边由MST性质可知一定图中一定存在至少一个最小生成树，是包含这条边的。现在u,v构成新的集合U\u0026#39;，V-U集合中去掉v构成另一个新的集合(V-U)\u0026#39;，现在，再选取一条带权最小的连边(u\u0026#39;,v\u0026#39;)，其中u\u0026#39;属于集合U\u0026#39;,v\u0026#39;属于集合(V-U)\u0026#39;，由MST性质又可知一定至少存在一个最小生成树，它包含这条边。现在，包含边（u-v）的最小生成树是否也包含边(u\u0026#39;-v\u0026#39;)呢？可以证明，包含边(u-v)的最小生成树中一定存在至少一棵最小生成树，它包含边(u\u0026#39;-v\u0026#39;)，可以用反证法证明，这里的思想和证明MST性质一样。假设包含边（u-v）的最小生成树中一定不存在包含边(u\u0026#39;-v\u0026#39;)的最小生成树，那么我任取包含边(u-v)的一棵最小生成树，可以划分它为两个集合，一个为P = U\u0026#39;，集合包含顶点u,u\u0026#39;，另一个为N = (V-U)\u0026#39;，它包含但不限于包含顶点v,v\u0026#39;，由于最小生成树也是连通图，那么这两个集合之间一定存在连边，由假设可知，这个连边至少不是(u\u0026#39;-v\u0026#39;)，而可能是其他的连边，不妨设为(a,b),a和b代表集合中的顶点。现在，连接边(u\u0026#39;-v\u0026#39;)，此时最小生成树中必有环，且在由两个集合P和N顶点所构成的子图中，一定是连通图，即a,u,u\u0026#39;一定连通，b,v,v\u0026#39;一定也连通，现在删去边(a,b)，两个集合之间依然连通，集合之中也保持连通，边的个数不边，仍然是一棵最小生成树，且是包含边（u\u0026#39;,v\u0026#39;）的一棵最小生成树，故可知假设错误，即包含边(u-v)的最小生成树中也一定存在包含边(u\u0026#39;-v\u0026#39;)的最小生成树。Prim算法正是一步一步运用这种性质构造树的，所以最终的生成树一定是一棵最小生成树。
【为啥Prim算法求出的就是最小生成树】 如果能看理解书上的MST性质，完全可以自己证明，我想也是严奶奶没给证明的原因，她相信我们看完后可以自己证明的。
■网友
维基百科有证明，而且非常短
推荐阅读
- 为啥看到书柜上的藏书会有心旷神怡的感觉
- 为啥知乎上普便有一种【我在北上广深打工，所以拥有更好的视野】这样的错觉
- 为啥工商银行的用户体验如此之差
- 汽车|看了中消协4S店服务测评调查结果，终于知道法系车为啥卖不好了
- 你为啥从窝窝商城离职?
- 为啥5G和2.4G默认的BSSID是相同的
- 为啥电器实体店的价格比淘宝贵那么多
- 现在在线学习视频有很多了，为啥大部分人还是喜欢下载下来观看
- 为啥到现在你还没有女朋友 ?
- 天赐的声音|33岁张雨绮为啥总离婚？看过这些照片就明白了，都是性感惹得祸