#include "p278.cpp"
#include "IOSTREAM.H"
#include "p43&47.cpp"




const int MaxNumEdges = 50;							//最大邊數
#ifndef SetMaxVertices
#define SetMaxVertices
const int MaxNumVertices=10;							//最大頂點數
#endif




template <class NameType, class DistType> class Graph {			//圖的類定義
private:
   SeqList<NameType> VerticesList;//( MaxNumVertices );			//頂點表
   DistType Edge[MaxNumVertices][MaxNumVertices];			//鄰接矩陣
   int CurrentEdges;								//當前邊數
   int FindVertex ( SeqList<NameType> & L, const NameType & vertex )
     { return L.Find (vertex); }     //在頂點表L中搜索頂點vertex
   int GetVertexPos ( const NameType & vertex )
     { return FindVertex (VerticesList, vertex ); }
     //給出頂點vertex在圖中的位置
public:
   Graph ( const int sz=MaxNumEdges );					//構造函數
   int GraphEmpty ( ) const { return VerticesList.IsEmpty ( ); }		//判圖空否
   int GraphFull ( ) const { return VerticesList.IsFull ( ) || CurrentEdges ==MaxNumEdges; }
   int NumberOfVertices ( ) { return VerticesList.Length(); }			//返回當前頂點數
   int NumberOfEdges ( ) { return CurrentEdges; }				//返回當前邊數
   NameType GetValue ( const int i )						//取頂點i的值, i不合理則返回空
      { return VerticesList.Get(i); }
   DistType GetWeight ( const int v1, const int v2 );		//給出以頂點v1和v2為兩端點的邊上的權值
   int GetFirstNeighbor ( const int v );				//給出頂點位置為v的第一個鄰接頂點的位置
   int GetNextNeighbor ( const int v1, const int v2 );		//給出頂點位置v1的某鄰接頂點v2的下一個鄰接頂點
   void InsertVertex (  NameType & vertex );		//插入一個頂點vertex, 該頂點沒有入邊
   void InsertEdge ( const int v1, const int v2, DistType weight );	//插入一條邊(v1, v2), 該邊上的權值為weight
   void RemoveVertex ( const int v );				//在圖中刪去頂點vertex和所有與它相關聯的邊
   void RemoveEdge ( const int v1, const int v2 );		//在圖中刪去邊(v1,v2)
   void Prim ( MinSpanTree &T ) ;
   void Kruskal ( MinSpanTree &T );
   friend istream& operator >>(istream& , Graph&);
};

template <class NameType, class DistType> Graph<NameType, DistType>::Graph ( const int sz ) {
//構造函數
   for ( int i=0; i<sz; i++ )					//鄰接矩陣初始化
	 for ( int j=0; j<sz; j++ ) Edge[i][j] = 0;
   CurrentEdges = 0;						//圖中當前邊數初始化
};

template <class NameType, class DistType>
DistType Graph<NameType, DistType>::GetWeight ( const int v1, const int v2 ) 
{
//給出以頂點v1和v2為兩端點的邊上的權值
   if ( v1 != -1 && v2 != -1 ) return Edge[v1][v2];
   else return NULL;							//帶權圖中權值為0, 表示無權值
};


template <class NameType, class DistType> 
int Graph<NameType, DistType>::GetFirstNeighbor ( const int v ) {
//給出頂點位置為v的第一個鄰接頂點的位置, 如果找不到, 則函數返回-1。
   if ( v != -1 ) {
	 for ( int col=0; col<VerticesList.Length(); col++ ) if ( Edge[v][col] > 0 ) return col;
   }
   return -1;
};

template <class NameType, class DistType>
int Graph<NameType, DistType>::GetNextNeighbor ( const int v1, const int v2 ) {
//給出頂點v1的某鄰接頂點v2的下一個鄰接頂點
   if ( v1 != -1 && v2 != -1 )
   {
     for ( int col=v2+1; col<VerticesList.Length(); col++ )
       if ( Edge[v1][col] > 0 ) return col;
   }
   return -1;
};

template <class NameType, class DistType>
void Graph<NameType, DistType>::InsertVertex (  NameType & vertex )		//插入一個頂點vertex, 該頂點沒有入邊
{
	assert (VerticesList.Insert ( vertex, VerticesList.Length() ));		
};

template <class NameType, class DistType>
void Graph<NameType, DistType>:: InsertEdge ( const int v1, const int v2, DistType weight )	//插入一條邊(v1, v2), 該邊上的權值為weight
{
	CurrentEdges++;
	Edge[v1][v2]=weight;
};
template <class NameType, class DistType>
istream& operator >>(istream& is, Graph<NameType,DistType>& g)
{
   int n,e,k,j;
   NameType head,tail,name;
   DistType weight;
   is >> n;										//輸入頂點個數
   for ( int i=0; i<n; i++)
   {
     is >> name;
     g.InsertVertex ( name );
   }		//依次輸入頂點, 插入圖中

   is >> e;										//輸入邊數

   for ( i=0; i<e; i++) {								//依次輸入邊信息
	 is >> tail >> head >> weight;						//輸入各邊
	 k = g.GetVertexPos ( tail );  j = g.GetVertexPos ( head );			//取兩頂點位置
	 g.InsertEdge ( k, j, weight );							//插入圖中
   }
   return is;

}