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這個數組是關鍵，它記錄了目前生成樹與每個結點的距離，當每次新加入一個結點，我們就要修正加入這個結點之後的這顆新的生成樹到每個結點的距離，因為原來到某個結點的距離，一定有新加入到某個結點的距離短