概述
Prim算法是应用贪心算法设计策略实现的生成最小支撑树的算法，又称为加点法。与其类似的是Kruskal算法，又称为加边法。
什么是最小支撑树
MST性质及其证明
Prim和kruskal都是贪心策略。
都是利用了MST性质。
Prim算法基本思想
设G=(V,E) 是一个连通赋权图，V={1，2，...,n}。
1. 设置一个空集S。
2. 随机选择一个顶点作为起始加入S，例如加入1，S={1}.
3. 作贪心选择：从V-S中选取 j 加入S，j 要满足<i,j>为最小，i∈S。
4. 重复3直至S中包含所有顶点。
Prim算法C实现
1.算法描述
关键之处在于如何选择最小的<i,j>,因此设置两个数组lowcost，closest。
lowcost[i] = Min(lowcost[i],<i,j>) ,j∈S。
lowcost[i]存储V-S中 i 顶点到S各顶点的边中的最小边权值,例如，S中有顶点1，2，则lowcost[i] = MIn{ <i,1>,<i,2>}。
closest[i] 存储lowcost[i]最小边的另一顶点。
S中有顶点1，2，则lowcost[i] = MIn{ <i,1>,<i,2>}，假设<i,2>最小则closest[i]=2。
故prim算法可分为如下3部分
1. 初始化lowcost和closest数组，和S数组（S[i]=1,表示i顶点已经进入S集和)
选择一个初始顶点start，lowcost初始化，lowcost[i]=<i,start>,closest[i]=start。
2. 找到遍历 lowcost 找最小，如lowcost[k]最小且k不在S中，k加入S，k∈V-S。
3. k加入S后 要更新lowcost和closest。
此时遍历lowcost，locost[i] = Min{Min(lowcost[i],<i,k>) },k为刚加入S中的顶点，i∈V-S。
若lowcost[i] > <i,k> ，则lowcost[i] = <i，k>,closest[i] = k.
4.重复2，3直至S中包含所有顶点。
2.代码
void Prim(int *lowcost,int *closest,Graph G)
{
int count=1,min,*s,start,k，*lowcost,*closest;
s = malloc((G->n+1)*sizeof(int));
start =1;
lowcost = malloc((G->n+1)*sizeof(WItem));
closest = malloc((G->n+1)*sizeof(int));
// 初始化数组
for(int i=1;i<=G->n;i++){
lowcost[i] = G->a[i][start];
closest[i]=start;
s[i]=0;
}
s[start]=1;printf(" %d ",start);
while(count<G->n){
// 找最小边
min = G->NoEdge;
for(int i=1;i<=G->n;i++ )
if(lowcost[i]<min && (!s[i]))
{
min = lowcost[i];
k=i;
}
// k加入S
s[k]=1;
count++;
printf(" %d ",k);
// 更新数组
for(int i=1;i<=G->n;i++)
if(G->a[i][k] < lowcost[i] && (!s[i]))
{ lowcost[i] = G->a[i][k];
closest[i] = k;
}
}// while
}
