prim算法是基于什么原理？

Kruskal算法求最小生成树的证明
0.说明：
G-图，Tmin-最小生成树，N-顶点数，M-边数；
因为，G存在Tmin，是G连通的充要条件；
所以，对于一个有N个顶点，M条边的连通图G而言，必定存在最小生成树Tmin；
假设把M条边按权重的大小以从小到大的顺序排列成e1,e2,...em;
再把N个顶点看作是N棵包含一个节点的最小生成树,均为G的最小生成树的子树；

1.下面反证第一次选择的最小权重边e1一定是这个图最小生成树可能的一种情况(图的最小生成树不唯一)Tmin的一条边:
证明：如果e1不是Tmin的边；
那么，把e1加入到Tmin中，即把树中两个节点用另一条边连接起来，这样必然形成了一条环；
如果断掉这个环中的另一条边，那么肯定就形成了另一棵权重和小于Tmin的生成树；
与最小生成树结论矛盾；
所以此分结论得证。
这样就可以认为e1连接起来的两个子树形成一个新的最小生成子树。
2.第二次从剩下的边里选择最小权重的边：
1） 如果这条边连接的两个点在一个子树上，
那么就形成了一个环，而显然这条边不比子树上的边权重小，
所以这条边不属于这个最小生成树；
2） 如果这条最小边连接的不同的子树；那么情况就与1中第一次选择的情况相同
这条边必定属于某个情况的最小生成树；
这样最小生成树的子树得到更新；
3.以后的情况均与第二次完全相同，直到找到N-1条边，就会使全部顶点构成连通集，
并且一定是一棵权重最小的树（选择的过程中避免了环的形成）；
如若找不到N-1条边，那么G就不是一个连通的图
Prim算法证明
1. 选择任意顶点S为初始点，下面证明与S点相连的最小边ES0一定属于Tmin（与Kruskal的第一步证明类似）：
证明：假设ES0不属于Tmin的边；
现把ES0加到Tmin中，则构成回路；
再把回路上与S点相连的另一条边断开，则形成了另一棵权重更小的树，
这样就与最小生成树的定义相矛盾；
所以ES0一定属于某个最小生成树；
鉴于此，我们就可以把S点、ES0以及边相连的另一个顶点Q，组成一个整体，看做是新的节点S.
2.通过1中的假设，得到了一个新的图，重复1中的过程，直到所有点都成了一个整体；
那么最后得到的树一定是G的最小生成树；
同样的如果找不到N-1条边，那么G就是不连通的，不存在最小生成树

贪心
具体证明可以看《算法导论》最小生成树那章