graph.h

这是本人精心搜集的关于常用图论算法的一套源码

//由于两种类型互相引用,故预先声明
//对图中顶点类型进行声明
template <class TYPE>
struct Vertex;
//声明弧的类型
template <class TYPE>
struct Arc;
//顶点类型的定义
template <class TYPE> 
struct Vertex{  
	Vertex<TYPE> *pNextVertex;   
	TYPE data;   
	int inDegree;   
	int outDegree;   
	short processed;   
	Arc<TYPE> *pArc;
}; 

//弧类型的定义
template <class TYPE>
struct Arc{  
	Vertex<TYPE> *destination;   
	Arc<TYPE> *pNextArc;
};

//图结构的类Graph的声明
template <class TYPE, class KTYPE> 
class Graph
{  private:      
		int count;           //图中顶点个数      
		Vertex<TYPE> *first; //图中顶点链表的头指针   
   public:      
		Graph();      
		~Graph();      
		void  insertVertex(TYPE dataIn);      
		int  deleteVertex(KTYPE dltKey);      
		int  insertArc(KTYPE  fromKey, KTYPE  toKey);      
		int  deleteArc(KTYPE  fromKey, KTYPE  toKey);      
		int  retrieveVertex(KTYPE  key, TYPE& DataOut);      
		int  firstArc(KTYPE  key,  TYPE& dataOut);      
		bool emptyGraph();      
		int  graphCount();  
		void outputGraph();

		void depthFirstTraverse(void (*visit)(TYPE& info));      
		void breadthFirstTraverse(void (*visit)(TYPE& info));
		void toplogicalSortDepthFirst(void (*visit)(TYPE &data)); 
};