基本思想：
1 置S={1}
2 只要S是V的真子集就做如下的贪心选择：
选取满足条件的i ，i属于S，j输入V-S，且c[i][j]最小的边，并将定点j加入S中
这个过程直到S==V为止。
3 这个过程所选的边，恰好就是最小生成树
算法描述：
void Prim(int n,Type * * c) { T = 空集; S = {1}; while(S != V) { (i,j)=i 属于 S 且 j属于V-S的最小权边; T = T∪{(i,j)}; S = S ∪ {j}; } }
模版代码：
template <class Type> vodi Prim(int n,Type * * c) { Type lowcost[maxint]; int closest[maxint]; bool s[maxint]; s[1] = true; for(int i=2;i<=n;i++) { lowcost[i] = c[1][i]; closest[i] = 1; s[i] = false; } for(int i = 1;i<n;i++) { Type min = inf; int j = 1; for(int k = 2;k <= n;k++) if((lowcost[k]<min) && (!s[k])) { min = lowcost[k]; j=k; } cout<<j<<' '<<closest[j]<<endl; s[j] = true; for(k = 2;k<= n;k++) if((c[j][k]<lowcost[k])&&(!s[k])) { lowcost[k] = c[j][k]; closest[k] = j; } } }
本文转自博客园xingoo的博客，原文链接：Prim算法-最小生成树，如需转载请自行联系原博主。
