network.h

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

//由于两种类型互相引用,故预先声明
//对网中顶点类型进行声明
template <class TYPE>
struct Vertex;

//声明边的类型
template <class TYPE>
struct Edge;

//顶点类型的定义
template <class TYPE> 
struct Vertex
{  Vertex<TYPE> *pNextVertex;   
	TYPE data;   
	int degree;   
	short inTree;   
	Edge<TYPE> *pEdge;
}; 

//边类型的定义
template <class TYPE>
struct Edge
{  Vertex<TYPE> *destination;   
   int weight;   
   short inTree;   
   Edge<TYPE> *pNextEdge;
};

//网结构的类Network的声明
template <class TYPE, class KTYPE> 
class Network
{private:      
   int count; //网中顶点个数      
   Vertex<TYPE> *first; //网中顶点链表的头指针   
 public:      
   Network();      
   ~Network();      
   void  insertVertex(TYPE dataIn);
   bool  insertEdge(KTYPE  fromKey, KTYPE  toKey, int w);
   void MSTKruskal();
   void MSTPrim();
   void outputNetwork();
};