#define NULL 0

template <class NameType, class DistType> class Graph;				//圖的前視類定義

template <class NameType,class DistType> class Edge {				//邊的定義
public:
   friend class Graph<NameType,DistType>;	
   int dest;							//邊的另一頂點位置, 第一個頂點位置是隱式的
   DistType cost;						//邊上的權值
   Edge<NameType,DistType> *link;						//下一條邊鏈指針
   Edge ( ) { }								//構造函數
   Edge ( int D, DistType C ) : dest (D), cost (C), link (NULL) { }	//構造函數
   int operator != ( const Edge &E ) const { return dest != E.dest; }
};

template <class NameType, class DistType> class Vertex {		//頂點的定義
public:
   friend class Graph<NameType,DistType>;	
   NameType data;							//頂點的名字
   Edge<NameType,DistType> *adj;							//出邊表的頭指針
};
#ifndef SetMaxVertices
#define SetMaxVertices
const int MaxNumVertices=10;
#endif
const DefaultSize = 20;
template <class NameType, class DistType> class Graph
{		//圖的類定義
//friend class Vertex <NameType, DistType>;
//friend class Edge<DistType>;
protected:
   Vertex<NameType, DistType> *NodeTable;			//頂點表 (各邊鏈表的頭結點)
   int NumVertices;							//當前頂點個數
   int MaxNumVertices;							//最大頂點個數
   int NumEdges;								//當前邊數
   int GetVertexPos ( const NameType & vertex );				//給出頂點vertex在圖中的位置
public:
   Graph (const int sz=DefaultSize );								//構造函數
   ~Graph ( );								//析構函數
   int GraphEmpty ( ) const { return NumVertices == 0; }		//測試圖空否
   int GraphFull ( ) const							//測試圖滿否
	  { return NumVertices == MaxNumVertices||NumEdges ==MaxNumEdges; }
   int NumberOfVertices ( ) { return NumVertices; }			//返回圖的頂點數
   int NumberOfEdges ( ) { return NumEdges; }			//返回圖的邊數
   NameType GetValue ( const int i )					//取位置為i的頂點中的值
	  { return i >= 0 && i < NumVertices ? NodeTable[i].data : NULL; }
   void InsertVertex ( const NameType & vertex );			//在圖中插入一個頂點
   void RemoveVertex ( const int v );					//在圖中刪除一個頂點
   void InsertEdge ( const int v1, const int v2, const DistType weight );		//在圖中插入一條邊
   void RemoveEdge ( const int v1, const int v2 );			//在圖中刪除一條邊
   DistType GetWeight ( const int v1, const int v2 );			//返回邊上的權值
   int GetFirstNeighbor ( const int v );				//取頂點v的第一個鄰接頂點
   int GetNextNeighbor ( const int v1, const int v2 );		//取頂點v1的某鄰接頂點v2的下一個鄰接頂點
   void DFS ( );
   void DFS ( const int v, int visited [ ] );
   void BFS ( int v );
   void DfnLow ( const int x );
   void DfnLow ( const int u, const int v );
   void Components ( );
   void Biconnected ( );
   void Biconnected ( const int u, const int v );

   void CriticalPath();
};