#include "p263.cpp"

template <class NameType,class DistType>
void Graph<NameType, DistType>::Prim ( MinSpanTree &T ) {
   int NumVertices = VerticesList.Length();				//圖中頂點數
   if (NumVertices<=0) return;
   int *lowcost,*nearvex;
   lowcost = new int[NumVertices];				//創建輔助數組
   nearvex = new int[NumVertices];				//創建輔助數組TV
   for ( int i=1; i<NumVertices; i++ ) {
	 if (Edge[0][i]==0) lowcost[i]=MAXINT; else lowcost[i] = Edge[0][i];  
	 nearvex[i] = 0;		//頂點0到各邊的代價及最短帶權路徑
   }
   nearvex[0] = -1;							//頂點0加到生成樹頂點集合, 用-1表示
   
   for ( i=1; i<NumVertices; i++ ) {				//循環-1次, 加入n-1條邊
	 int min = MAXINT;  int v = 0;				//求生成樹外頂點到生成樹內頂點具有最小權值的邊
	 for ( int j=0; j<NumVertices; j++ )			//確定當前具最小權值的邊及頂點位置
	   if ( nearvex[j] != -1 && lowcost[j] < min ) { v = j;  min = lowcost[j]; }
	 if ( v ) 
	 {									// v==0表示再也找不到要求的頂點了
	   T.addEdge(nearvex[v],v,lowcost[v]);	   
	   nearvex[v] = -1;						//加入生成樹頂點集合
	   for ( j=1; j<NumVertices; j++ )
		 if ( (nearvex[j] != -1) && (Edge[v][j]!=0) && (Edge[v][j] < lowcost[j]) )
		   { lowcost[j] = Edge[v][j];  nearvex[j] = v; }		//修改
	 }
   }   
}