#include "P265.cpp"#include "iostream.h"#include "assert.h"const int MaxNumEdges=100;template <class NameType, class DistType>Graph <NameType, DistType>::Graph ( const int sz=DefaultSize ) : NumVertices (0), MaxNumVertices (sz), NumEdges (0) {   int n, e, k, j;   NameType name, tail, head;   DistType weight;   NodeTable = new Vertex<NameType,DistType>[MaxNumVertices];			//創建頂點表數組   cin >> n;										//輸入頂點個數      assert(n<=sz);      for ( int i=0; i<n; i++)   {     cin >> name;     InsertVertex ( name );   }		//依次輸入頂點, 插入圖中   cin >> e;										//輸入邊數      assert(e<=MaxNumEdges);      for ( i=0; i<e; i++) {								//依次輸入邊信息	 cin >> tail >> head >> weight;						//輸入各邊	 k = GetVertexPos ( tail );  j = GetVertexPos ( head );			//取兩頂點位置	 InsertEdge ( k, j, weight );							//插入圖中   }}template <class NameType, class DistType> Graph<NameType, DistType>::~Graph ( ) {   for ( int i=0; i<NumVertices; i++ ) {						//刪除各邊鏈表中的結點	 Edge<NameType,DistType> *p = NodeTable[i].adj;	 while ( p != NULL ) 							//循環刪除	   {	NodeTable[i].adj = p->link;  delete p;  p = NodeTable[i].adj; }   }   delete [ ] NodeTable;								//刪除頂點數組}template <class NameType, class DistType>int Graph<NameType, DistType>::GetVertexPos( const NameType & vertex ){   for ( int i=0; i< NumVertices; i++) {	 if ( NodeTable[i].data == vertex ) return i;   }   return -1;}template <class NameType, class DistType> int Graph<NameType, DistType>::GetFirstNeighbor ( const int v ) {//給出頂點位置為v的第一個鄰接頂點的位置, 如果找不到, 則函數返回-1。   if ( v != -1 ) {							//v存在	 Edge<NameType,DistType> *p = NodeTable[v].adj;				//邊鏈表第一個結點地址	 if ( p != NULL ) return p->dest;				//有, 返回該邊另一個頂點   }   return -1;								//沒有邊}template <class NameType, class DistType>int Graph<NameType, DistType>::GetNextNeighbor ( const int v1, const int v2 ) {//給出頂點v1的某鄰接頂點v2的下一個鄰接頂點的位置, 若沒有下一個鄰接頂點, 則函數返回-1。   if ( v1 != -1 ) {									//v1存在	 Edge<NameType,DistType> *p = NodeTable[v1].adj;				//邊鏈表第一個結點地址	 while ( p != NULL ) {							//尋找第v2個鄰接頂點	   if ( p->dest == v2 && p->link != NULL ) return p->link->dest;	   else p = p->link;	 }   }   return -1;}template <class NameType, class DistType>DistType Graph<NameType, DistType>::GetWeight ( const int v1, const int v2) {//函數返回邊(v1, v2)上的權值, 若該邊不在圖中, 則函數返回權值0。   if ( v1 != -1 && v2 != -1 ) {	 Edge<NameType,DistType> *p = NodeTable[v1].adj;				//邊鏈表頭指針	 while ( p != NULL ) {	   if ( p->dest == v2 ) return p->cost;				//找到此邊, 返回權值	   else p = p->link;							//否則找下一條邊	 }   }   return 0;										//邊不在圖中}