4---------最小生成树--prim算法

用prim算法构造最小生成树的思路比较简单，实际上也是贪心算法的一种，依次遍历每个结点，寻找与当前生成树最小的结点，值得注意的是，不是到当前结点的最短路径，而是寻找与当前生成树最小的结点

/**
*	prim算法
*	思路：从某个结点开始，依次构造最小生成树，每次构造，都需要修正当前生成树到每条边的距离
*/
void prim(MGraph * G,int v0){
	int sum;
	//第一个数组用来记录与当前生成树的相关的最短边，第二个数组用来记录是否已经加入到最小生成树
	int lowcast[maxSize],visited[maxSize];
	int i,j,v,min;
	for(i=0;i<G->n;i++){
		visited[i] = 0;	//将所有结点都设置成未标记状态
		lowcast[i] = G->edges[v0][i];
	}
	visited[v0] = 1;	//先标记第一个结点
	printf("%c",G->nodes[i].data);	//遍历该顶点，可以换成其他操作
	for(i=0;i<G->n-1;i++){	//n-1的原因是当如果只剩下两个结点的时候，那么这两个结点就不用再赛选了
		min = INF;	//用来记录最小值，主要用来求生成树的总权值
		for(j=0;j<G->n;j++){
			if(!visited[j]&&lowcast[j]<min){
				min = lowcast[i];	
				v = j;	//记录当前最小的结点
			}
		}
		sum += min;
		visited[v] = 1;	//加入到最小生成树
		//由于加入了新结点，那么应该更新原来生成树中对每个结点的最短边，下面这个循环用来修正
		for(j=0;j<G->n;j++){		
			if(!visited[j] && G->edges[v][j] < lowcast[j]){	//修正当前生成树到还没有加入结点的记录
				lowcast[j] = G->edges[v][j];
			}
		}
	}
	printf("%d",sum);
}
           

lowcast这个数组是关键，它记录了当前生成树与每个结点的距离，当每次新加入一个结点，我们就要修正加入这个结点之后的这颗新的生成树到每个结点的距离，因为原来到某个结点的距离，一定有新加入到某个结点的距离短