求最小生成树-Prim（普里姆算法）

普里姆算法时间复杂度为O(V^2)，适用于稠密图

#include <iostream>
using namespace std;
#define Maxsize 100
typedef char VertexType;
typedef int EdgeType;
typedef struct{
	VertexType Vex[Maxsize];
	EdgeType edge[Maxsize][Maxsize];
	int vexnum,arcnum;
}MGraph;

//Prim-普里姆算法
void Prim(MGraph G,int v0,int &sum){
	int lowcost[Maxsize],vset[Maxsize],v;
	int i,j,k,min;
	v=v0;
	for(i=0;i<G.vexnum;i++){
		lowcost[i]=G.edge[v0][i];	//初始化最短边 
		vset[i]=0;	//初始化树集合 
	} 
	vset[v0]=1;	//将v0并入树中 
	sum=0;	//树权值初始化 
	for(i=1;i<G.vexnum;i++){
		min=INF;	//INF是已经定义的比图中所有权值都大的常量
		for(j=0;j<G.vexnum;j++)
			if(vset[j]==0&&lowcost[j]<min){
				//选出当前生成树到其余顶点
				min=lowcost[j];
				k=j;	//记录树到其余顶点最短边对应点 
			} 
		vset[k]=1;	//加入树集合
		v=k;
		sum+=min;
		for(j=0;j<G.vexnum;j++)
			if(vset[j]==0&&G.edge[v][j]<lowcost[j])
				lowcost[j]=G.edge[v][j];	//更新最短边 
	}
}