#include "p278.cpp"#include "IOSTREAM.H"#include "p43&47.cpp"const int MaxNumEdges = 50;							//最大邊數(shù)#ifndef SetMaxVertices#define SetMaxVerticesconst int MaxNumVertices=10;							//最大頂點(diǎn)數(shù)#endiftemplate <class NameType, class DistType> class Graph {			//圖的類定義private:   SeqList<NameType> VerticesList;//( MaxNumVertices );			//頂點(diǎn)表   DistType Edge[MaxNumVertices][MaxNumVertices];			//鄰接矩陣   int CurrentEdges;								//當(dāng)前邊數(shù)   int FindVertex ( SeqList<NameType> & L, const NameType & vertex )     { return L.Find (vertex); }     //在頂點(diǎn)表L中搜索頂點(diǎn)vertex   int GetVertexPos ( const NameType & vertex )     { return FindVertex (VerticesList, vertex ); }     //給出頂點(diǎn)vertex在圖中的位置public:   Graph ( const int sz=MaxNumEdges );					//構(gòu)造函數(shù)   int GraphEmpty ( ) const { return VerticesList.IsEmpty ( ); }		//判圖空否   int GraphFull ( ) const { return VerticesList.IsFull ( ) || CurrentEdges ==MaxNumEdges; }   int NumberOfVertices ( ) { return VerticesList.Length(); }			//返回當(dāng)前頂點(diǎn)數(shù)   int NumberOfEdges ( ) { return CurrentEdges; }				//返回當(dāng)前邊數(shù)   NameType GetValue ( const int i )						//取頂點(diǎn)i的值, i不合理則返回空      { return VerticesList.Get(i); }   DistType GetWeight ( const int v1, const int v2 );		//給出以頂點(diǎn)v1和v2為兩端點(diǎn)的邊上的權(quán)值   int GetFirstNeighbor ( const int v );				//給出頂點(diǎn)位置為v的第一個(gè)鄰接頂點(diǎn)的位置   int GetNextNeighbor ( const int v1, const int v2 );		//給出頂點(diǎn)位置v1的某鄰接頂點(diǎn)v2的下一個(gè)鄰接頂點(diǎn)   void InsertVertex (  NameType & vertex );		//插入一個(gè)頂點(diǎn)vertex, 該頂點(diǎn)沒有入邊   void InsertEdge ( const int v1, const int v2, DistType weight );	//插入一條邊(v1, v2), 該邊上的權(quán)值為weight   void RemoveVertex ( const int v );				//在圖中刪去頂點(diǎn)vertex和所有與它相關(guān)聯(lián)的邊   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 ) {//構(gòu)造函數(shù)   for ( int i=0; i<sz; i++ )					//鄰接矩陣初始化	 for ( int j=0; j<sz; j++ ) Edge[i][j] = 0;   CurrentEdges = 0;						//圖中當(dāng)前邊數(shù)初始化};template <class NameType, class DistType>DistType Graph<NameType, DistType>::GetWeight ( const int v1, const int v2 ) {//給出以頂點(diǎn)v1和v2為兩端點(diǎn)的邊上的權(quán)值   if ( v1 != -1 && v2 != -1 ) return Edge[v1][v2];   else return NULL;							//帶權(quán)圖中權(quán)值為0, 表示無權(quán)值};template <class NameType, class DistType> int Graph<NameType, DistType>::GetFirstNeighbor ( const int v ) {//給出頂點(diǎn)位置為v的第一個(gè)鄰接頂點(diǎn)的位置, 如果找不到, 則函數(shù)返回-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 ) {//給出頂點(diǎn)v1的某鄰接頂點(diǎn)v2的下一個(gè)鄰接頂點(diǎn)   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 )		//插入一個(gè)頂點(diǎn)vertex, 該頂點(diǎn)沒有入邊{	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), 該邊上的權(quán)值為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;										//輸入頂點(diǎn)個(gè)數(shù)   for ( int i=0; i<n; i++)   {     is >> name;     g.InsertVertex ( name );   }		//依次輸入頂點(diǎn), 插入圖中   is >> e;										//輸入邊數(shù)   for ( i=0; i<e; i++) {								//依次輸入邊信息	 is >> tail >> head >> weight;						//輸入各邊	 k = g.GetVertexPos ( tail );  j = g.GetVertexPos ( head );			//取兩頂點(diǎn)位置	 g.InsertEdge ( k, j, weight );							//插入圖中   }   return is;}