Prim算法主要的思路：将点集一分为二，通过找到两个点集之间的最短距离，来确定最小生成树，每次确定最短距离后，对两个点集进行更新。
具体的实现过程：难点就是如何找到两个点集之间的最短距离，这里设置两个数组，lowcost[i],mst[i],分别表示以i为终点的边和对应的起点，有了这两个数组就能够顺利的进行状态更新了。（整个代码与dijstra算法惊人的相似），大家可以将两者对比起来看。
代码：
#include <iostream>
#define INF 99999999
#include <string.h>
using namespace std; int a[][];
int lowcost[];//lowcost[i]表示以i为终点的最短距离，
int mst[];//mst[i]对应的lowcost[i]的起点 //默认的起点为1
void prim(int n){
int minl,tmp;
int flag[];
for(int i=;i<=n;i++)
mst[i]=;
for(int i=;i<=n;i++)
lowcost[i]=a[][i];
memset(flag,,sizeof(flag));
for(int k=;k<=n;k++){
minl=INF;
for(int i=;i<=n;i++){
if(flag[i]==&&lowcost[i]<minl){
minl=lowcost[i];
tmp=i;
}
}
cout<<'V'<<mst[tmp]<<" "<<'V'<<tmp<<" "<<minl<<endl;
for(int i=;i<=n;i++){
if(a[tmp][i]<lowcost[i]&&a[tmp][i]>){
lowcost[i]=a[tmp][i];
mst[i]=tmp;
}
}
flag[tmp]=;
}
} int main(){
int n,m;
int x,y,path;
cin>>n>>m;
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
if(i==j)
a[i][j]=;
else
a[i][j]=INF;
}
}
for(int i=;i<=m;i++){
cin>>x>>y>>path;
a[x][y]=a[y][x]=path;
}
prim(n);
return ;
}